2026-07-20T09:01:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1234 2024-03-06T11:07:37Z ddc:004 open_access

Approximating Solution Structure van Rooij, Iris Hamilton, Matthew Müller, Moritz Wareham, Todd Approximation Algorithms Solution Structure 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} Schloss Dagstuhl – Leibniz-Zentrum für Informatik Iris van Rooij and Matthew Hamilton and Moritz Müller and Todd Wareham 2007 Is Part Of Dagstuhl Seminar Proceedings, Volume 7281, Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs (2007) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.07281.3 urn:nbn:de:0030-drops-12345 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07281.3 eng https://creativecommons.org/licenses/by/4.0/legalcode