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 solutiondistance function $d$,
{em i.e.}, $d(A(x), y) leq h(x)$ for some $y in optsol(x)$. Such
structureapproximation algorithms have applications within Cognitive
Science and other areas. Though there is an
extensive literature dating back over 30 years on valueapproximation,
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
polynomialtime and fixedparameter structure(in)approximability of
combinatorial optimization problems relative to metric solutiondistance
functions, {em e.g.}, Hamming distance. We motivate this framework by
(1) describing a particular application within Cognitive Science and (2)
showing that valueapproximability does not necessarily imply
structureapproximability (and vice versa). This framework includes
definitions of several types of structure approximation algorithms
analogous to those studied in valueapproximation, as well as
structureapproximation problem classes and a
structureapproximabilitypreserving 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
(copresented 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 = {18624405},
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

Issue date: 

2007 
Date of publication: 

28.11.2007 