van Rooij, Iris ;
Hamilton, Matthew ;
Müller, Moritz ;
Wareham, Todd
Approximating Solution Structure
Abstract
hen it is hard to compute an optimal solution $y in optsol(x)$ to an
instance $x$ of a problem, one may be willing to settle for an efficient
algorithm $A$ that computes an approximate solution $A(x)$. The most
popular type of approximation algorithm in Computer Science (and indeed
many other applications) computes solutions whose value is within some multiplicative factor of the optimal solution value, {em e.g.},
$max(frac{val(A(x))}{optval(x)}, frac{optval(x)}{val(A(x))}) leq
h(|x|)$ for some function $h()$. However, an algorithm might also
produce a solution whose structure is ``close'' to the structure of an
optimal solution relative to a specified solution-distance function $d$,
{em i.e.}, $d(A(x), y) leq h(|x|)$ for some $y in optsol(x)$. Such
structure-approximation algorithms have applications within Cognitive
Science and other areas. Though there is an
extensive literature dating back over 30 years on value-approximation,
there is to our knowledge no work on general techniques for assessing
the structure-(in)approximability of a given problem.
In this talk, we describe a framework for investigating the
polynomial-time and fixed-parameter structure-(in)approximability of
combinatorial optimization problems relative to metric solution-distance
functions, {em e.g.}, Hamming distance. We motivate this framework by
(1) describing a particular application within Cognitive Science and (2)
showing that value-approximability does not necessarily imply
structure-approximability (and vice versa). This framework includes
definitions of several types of structure approximation algorithms
analogous to those studied in value-approximation, as well as
structure-approximation problem classes and a
structure-approximability-preserving reducibility. We describe a set of techniques for proving the degree of
structure-(in)approximability of a given problem, and summarize all
known results derived using these techniques. We also list 11 open
questions summarizing particularly promising directions for future
research within this framework.
vspace*{0.15in}
oindent
(co-presented with Todd Wareham)
vspace*{0.15in}
jointwork{Hamilton, Matthew; M"{u}ller, Moritz; van Rooij, Iris; Wareham, Todd}
BibTeX - Entry
@InProceedings{vanrooij_et_al:DSP:2007:1234,
author = {Iris van Rooij and Matthew Hamilton and Moritz M{\"u}ller and Todd Wareham},
title = {Approximating Solution Structure},
booktitle = {Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs},
year = {2007},
editor = {Erik Demaine and Gregory Z. Gutin and Daniel Marx and Ulrike Stege},
number = {07281},
series = {Dagstuhl Seminar Proceedings},
ISSN = {1862-4405},
publisher = {Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2007/1234},
annote = {Keywords: Approximation Algorithms, Solution Structure}
}
|
Keywords: |
|
Approximation Algorithms, Solution Structure |
|
Seminar: |
|
07281 - Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs
|
|
Documenttype: |
|
InProceedings |
|
Issue date: |
|
2007 |
|
Date of publication: |
|
28.11.2007 |
