Abstract
We outline a relatively new research agenda aiming at building a new approximation paradigm by matching two distinct domains, the polynomial approximation and the exact solution of NP -hard problems by algorithms with guaranteed and non-trivial upper complexity bounds. We show how one can design approximation algorithms achieving ratios that are “forbidden” in polynomial time (unless a very unlikely complexity conjecture is confirmed) with worst-case complexity much lower than that of an exact computation.
![](http://media.springernature.com/m312/springer-static/image/art%3A10.1007%2Fs10288-015-0294-7/MediaObjects/10288_2015_294_Fig1_HTML.gif)
Similar content being viewed by others
Notes
All the problems mentioned in the paper are defined in “Appendix”.
A polynomial time approximation schema is a sequence of algorithms parameterized by \(\epsilon > 0\) achieving approximation ratio \(1\pm \epsilon \) (depending on the optimization goal of the problem handled), for any \(\epsilon > 0\).
These are graph-problems, a feasible solution of which is a subset of vertices of the input-graph inducing a subgraph \(G'\) that satisfies some non-trivial hereditary property. A graph-property \(\pi \) is hereditary, if every subgraph of \(G'\) satisfies \(\pi \) whenever \(G'\) satisfies \(\pi \); it is non-trivial, if it is satisfied for infinitely many graphs and is false for infinitely many graphs.
The Exponential Time Hypothesis claims, informally, that for any k, k -sat cannot be solved in subexponential time.
References
Arora S, Lund C, Motwani R, Sudan M, Szegedy M (1998) Proof verification and intractability of approximation problems. J Assoc Comput Mach 45(3):501–555
Ausiello G, Crescenzi P, Gambosi G, Kann V, Marchetti-Spaccamela A, Protasi M (1999) Complexity and approximation. Combinatorial optimization problems and their approximability properties. Springer, Berlin
Avidor A, Berkovitch I, Zwick U (2006) Improved approximation algorithms for MAX NAE-SAT and MAX SAT. In: Erlebach T, Persiano G (eds) Proceedings of workshop on approximation and online algorithms, WAOA’05, vol 3879 of lecture notes in computer science. Springer, pp 27–40
Berge C (1973) Graphs and hypergraphs. North Holland, Amsterdam
Berman P, Fujito T (1995) On the approximation properties of independent set problem in degree 3 graphs. In: Proceedings of international workshop on algorithms and data structures, WADS’95, vol 955 of lecture notes in computer science. Springer, pp 449–460
Björklund A, Husfeldt T (2008) Exact algorithms for exact satisfiability and number of perfect matchings. Algorithmica 52(2):226–249
Björklund A, Husfeldt T, Koivisto M (2009) Set partitioning via inclusion–exclusion. SIAM J Comput 39(2):546–563
Bonnet E, Escoffier B, Kim E, Paschos VTh (2015) On subexponential and fpt-time inapproximability. Algorithmica 71(3):541–565
Boria N, Bourgeois N, Escoffier B, Paschos VTh (2013) Exponential approximation schemata for some network design problems. J Discrete Algorithms 22:43–52
Bourgeois N, Della Croce F, Escoffier B, Paschos VTh (2013) Fast algorithms for min independent dominating set. Discrete Appl Math 161(4–5):558–572
Bourgeois N, Escoffier B, Paschos VTh (2009) Efficient approximation of min set cover by moderately exponential algorithms. Theor Comput Sci 410(21–23):2184–2195
Bourgeois N, Escoffier B, Paschos VTh (2011) Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms. Discrete Appl Math 159(17):1954–1970
Byskov JM (2004) Enumerating maximal independent sets with applications to graph colouring. Oper Res Lett 32(6):547–556
Chalermsook P, Laekhanukit B, Nanongkai D (2013) Independent set, induced matching, and pricing: connections and tight (subexponential time) approximation hardnesses. In: Proceedings of FOCS’13, pp 370–379
Cygan M, Kowalik L, Wykurz M (2009) Exponential-time approximation of weighted set cover. Inf Process Lett 109(16):957–961
Cygan M, Pilipczuk M (2010) Exact and approximate bandwidth. Theor Comput Sci 411(40–42):3701–3713
Cygan M, Pilipczuk M, Wojtaszczyk JO (2010) Capacitated domination faster than \({O}(2^n)\). In: Kaplan H (eds) Proceedings of scandinavian symposium and workshops on algorithm theory, SWAT’10, vol 6139 of lecture notes in computer science. S**er, pp 74–80
Dantsin E, Gavrilovich M, Hirsch EA, Konev B (2002) max sat approximation beyond the limits of polynomial-time approximation. Ann Pure Appl Log 113:81–94
Dinur I (2007) The PCP theorem by gap amplification. J Assoc Comput Mach 54(3)
Escoffier B, Paschos VTh, Tourniaire E (2014) Approximating Max Sat by moderately exponential and parameterized algorithms. Theor Comput Sci 560(2):147–157
Fomin FV, Grandoni F, Kratsch D (2005) Measure and conquer: domination—a case study. In: Caires L, Italiano GF, Monteiro L, Palamidessi C, Yung M (eds) Proceedings of ICALP’05, vol 3580 of lecture notes in computer science. Springer, pp 191–203
Fomin FV, Kratsch D (2010) Exact exponential algorithms. EATCS. Springer, Berlin
Gurevich Y, Shelah S (1987) Expected computation time for Hamiltonian path problem. SIAM J Comput 16(3):486–502
Halldórsson MM (1993) Approximating the minimum maximal independence number. Inf Process Lett 46:169–172
Held M, Karp R (1962) A dynamic programming approach to sequencing problems. J SIAM 10:196–210
Hochbaum DS (ed) (1997) Approximation algorithms for NP-hard problems. PWS, Boston
Johnson DS (1974) Approximation algorithms for combinatorial problems. J Comput Syst Sci 9:256–278
Khot S, Regev O (2003) Vertex cover might be hard to approximate to within \(2-\varepsilon \). In: Proceedings of annual conference on computational complexity, CCC’03, pp 379–386
Moshkovitz D (2012) The projection games conjecture and the NP-hardness of \(\ln {n}\)-approximating set-cover. In Gupta A, Jansen K, Rolim JDP, Servedio RA (eds) Proceedings of workshop on approximation algorithms for combinatorial optimization problems and workshop on randomization and computation, APPROX-RANDOM’12, vol 7408 of lecture notes in computer science. Springer, pp 276–287
Nemhauser GL, Trotter LE (1975) Vertex packings: structural properties and algorithms. Math Program 8:232–248
Paluch KE, Mucha M, Madry A (2009) A 7/9-approximation algorithm for the maximum traveling salesman problem. In Dinur I, Jansen K, Naor J, Rolim JDP (eds) Proceedings of approximation, randomization and combinatorial optimization. Algorithms and techniques, APPROX-RANDOM’09, vol 5687 of lecture notes in computer science. Springer, pp 298–311
Papadimitriou CH, Steiglitz K (1981) Combinatorial optimization: algorithms and complexity. Prentice Hall, New Jersey
Papadimitriou CH, Yannakakis M (1991) Optimization, approximation and complexity classes. J Comput Syst Sci 43:425–440
Paschos VTh (2004) Complexité et approximation polynomiale. Hermès, Paris
Vazirani V (2001) Approximation algorithms. Springer, Berlin
Woeginger GJ (2003) Exact algorithms for NP-hard problems: a survey. In: Juenger M, Reinelt G, Rinaldi G (eds) Combinatorial optimization—Eureka! You shrink!, vol 2570 of lecture notes in computer science. Springer, pp 185–207
**ao M, Nagamochi H (2013) Exact algorithms for maximum independent set. CoRR, abs/1312.6260
Zuckerman D (2007) Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput 3(6):103–128
Acknowledgments
The very constructive suggestions and comments of two anonymous reviewers are gratefully acknowledged.
Author information
Authors and Affiliations
Corresponding author
Appendix
Appendix
1.1 A list of combinatorial problems
- max independent set::
-
Given a graph G(V, E), max independent set consists of finding a set \(S \subseteq V\) of maximum size such that for any \((u,v) \in S \times S\), \((u,v) \notin E\).
- max clique::
-
Given a graph G(V, E), max clique consists of finding a set \(K \subseteq V\) of maximum size such that for any \((u,v) \in K \times K\), \((u,v) \in E\).
- min set cover::
-
Given a set C of cardinality n and a system \(\mathcal {S} = \{S_1, \ldots , S_m\} \subset 2^C\), min set cover consists of determining a minimum size subsystem \(\mathcal {S}'\) such that \(\cup _{S \in \mathcal {S}'}S = C\).
- min vertex cover::
-
Given a graph G(V, E), min vertex cover consists of finding a set \(C \subseteq V\) of minimum size such that, for every \((u,v) \in E\), either u, or v belongs to C.
- min coloring::
-
Given a graph G(V, E), min coloring consists of partitioning the vertex-set V of G into a minimum number of independent sets.
- min independent dominating set::
-
Given a graph G(V, E), min independent dominating set consists of finding the smallest independent set of G that is maximal for the inclusion.
- capacitated dominating set::
-
Given a graph G(V, E) with each of its vertex v equipped with a number c(v) that represents the number of the other vertices that v can dominate, a set \(S \subset V\) is a capacitated dominating set if there exists a function \(f_{S}: V {\setminus } S \rightarrow S\) such that \(f_S(v)\) is a neighbor of v for each \(v \in V {\setminus } S\) and \(|f^{-1}_S(v)| \leqslant c(v)\). The goal here is to determine a capacitated dominating set of the smallest possible size.
- min bandwidth::
-
Given a graph G(V, E), the min bandwidth problem consists of labeling the vertices of V with distinct integers \(f(v_i)\), in such a way that the quantity \(\max \{|f(v_i) - f(v_j)|: v_iv_j \in E\}\) is minimized.
- max tsp::
-
Given a complete edge-weighted graph G, the objective is to determine a maximum-weight Hamiltonian cycle of G.
- bin packing::
-
Given an infinite number of bins \(B_1, \ldots ,\) with capacity 1, and a list of n items with sizes \(a_1,\dots ,a_n \in ~[0, 1]\), the objective is to pack them into a minimum number of bins with the constraint \(\sum _{i \in B_j}a_i \leqslant 1\).
- max sat::
-
Given a set of m disjunctive clauses over a set of n variables, max sat consists of finding a truth assignment for the variables that maximizes the number of satisfied clauses.
- k -sat::
-
Given a set of m disjunctive clauses, each of them containing at most k literals), over a set of n variables, does there exist a truth-assignment on the variables simultaneously satisfying all of them?
- hamiltonian path::
-
Given a graph G(V, E), does there exist a Hamiltonian path (i.e., a simple path that visits all the vertices of V) in G?
Rights and permissions
About this article
Cite this article
Paschos, V.T. When polynomial approximation meets exact computation. 4OR-Q J Oper Res 13, 227–245 (2015). https://doi.org/10.1007/s10288-015-0294-7
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10288-015-0294-7