License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.07281.3
URN: urn:nbn:de:0030-drops-12345
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2007/1234/
Go to the corresponding Portal

van Rooij, Iris ; Hamilton, Matthew ; Müller, Moritz ; Wareham, Todd

Approximating Solution Structure

pdf-format:
07281.vanRooijIris.Paper.1234.pdf (0.3 MB)

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:DagSemProc.07281.3,
  author =	{van Rooij, Iris and Hamilton, Matthew and M\"{u}ller, Moritz and Wareham, Todd},
  title =	{{Approximating Solution Structure}},
  booktitle =	{Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs},
  pages =	{1--24},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7281},
  editor =	{Erik Demaine and Gregory Z. Gutin and Daniel Marx and Ulrike Stege},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2007/1234},
  URN =		{urn:nbn:de:0030-drops-12345},
  doi =		{10.4230/DagSemProc.07281.3},
  annote =	{Keywords: Approximation Algorithms, Solution Structure}
}

Keywords: Approximation Algorithms, Solution Structure
Collection: 07281 - Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs
Issue Date: 2007
Date of publication: 28.11.2007

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI