Super-polynomial approximation branching algorithms

Escoffier, Bruno; Paschos, Vangelis Th.; Tourniaire, Emeric

RAIRO - Operations Research - Recherche Opérationnelle, Tome 50 (2016) no. 4-5, pp. 979-994.

We give sufficient conditions for deriving moderately exponential and/or parameterized time approximation schemata ($i.e.$, algorithms achieving ratios $1\pm ϵ$, for arbitrarily small $ϵ$) for broad classes of combinatorial optimization problems via a well-known technique widely used for deriving exact algorithms, namely the branching tree pruning.

Classification : 68W25, 05C85, 68Q25
Mots clés : Branching algorithm, moderately exponential approximation, approximation schema

G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela and M. Protasi, Complexity and approximation. Combinatorial optimization problems and their approximability properties. Springer-Verlag, Berlin (1999). | MR | Zbl

A. Becker and D. Geiger, Optimization of pearl’s method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem. Artif. Intell. 83 (1996) 167–188. | DOI | MR | Zbl

E. Bonnet, B. Escoffier, E. Kim and V.Th. Paschos, On subexponential and fpt-time inapproximability. In Proc. of International Workshop on Parameterized and Exact Computation, IPEC’13, edited by G. Gutin and S. Szeider. Vol. 8246 of Lect. Notes Comput. Sci. Springer-Verlag (2013) 54–65. | MR | Zbl

N. Bourgeois, B. Escoffier and V. Th. Paschos, Efficient approximation of min coloring by moderately exponential algorithms. Inform. Process. Lett. 109 (2009) 950–954. | DOI | MR | Zbl

N. Bourgeois, B. Escoffier and V. Th. Paschos. Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms. Discrete Appl. Math. 159 (2011) 1954–1970. | DOI | MR | Zbl

L. Brankovic and H. Fernau, Combining two worlds: parameterized approximation for vertex cover. In Proc. of International Symposium on Algorithms and Computation, ISAAC’10, edited by O. Cheong and K.-Y. Chwa ans K. Park. Vol. 6506 of Lect. Notes Comput. Sci. Spinger-Verlag (2010) 390–402. | MR | Zbl

L. Cai and X. Huang, Fixed-parameter approximation: conceptual framework and approximability results. In Proc. of International Workshop on Parameterized and Exact Computation, IWPEC’06, edited by H.L. Bodlaender and M.A. Langston. Vol. 4169 of Lect. Notes Comput. Sci. Springer-Verlag (2006) 96–108. | MR | Zbl

Y. Chen, M. Grohe and M. Grüber, On parameterized approximability. In Proc. of International Workshop on Parameterized and Exact Computation, IWPEC’06, edited by H.L. Bodlaender and M.A. Langston. Vol. 4169 of Lect. Notes Comput. Sci. Springer-Verlag (2006) 109–120. | MR | Zbl

F. Della Croce and V.Th. Paschos, Efficient algorithms for the max $k$-vertex cover problem. J. Comb. Optim. 28 (2014) 674–691. | DOI | MR | Zbl

M. Cygan and M. Pilipczuk, Exact and approximate bandwidth. Theoret. Comput. Sci. 411 (2010) 3701–3713. | DOI | MR | Zbl

E. Dantsin, M. Gavrilovich, E.A. Hirsch and B. Konev, max sat approximation beyond the limits of polynomial-time approximation. Ann. Pure Appl. Logic 113 (2002) 81–94. | DOI | MR | Zbl

F. Della Croce, M.J. Kaminski and V.Th. Paschos, An exact algorithm for max cut in sparse graphs. Oper. Res. Lett. 35 (2007) 403–408. | DOI | MR | Zbl

I. Dinur and M. Safra, The importance of being biased. In Proc. of STOC’02 (2002) 33–42. | MR | Zbl

R.G. Downey and M.R. Fellows, Parameterized complexity. Monogr. Comput. Sci. Springer, New York (1999). | MR | Zbl

R.G. Downey, M.R. Fellows and C. McCartin, Parameterized approximation problems. In Proc. of International Workshop on Parameterized and Exact Computation, IWPEC’06, edited by H.L. Bodlaender and M.A. Langston. Vol. 4169 of Lect. Notes Comput. Sci. Springer-Verlag (2006) 121–129. | MR | Zbl

B. Escoffier, V. Th. Paschos and E. Tourniaire, Approximating max sat by moderately exponential and parameterized algorithms. In Proc. of Theory and Applications of Models of Computation, TAMC’12, edited by M. Agrawal, S. Barry Cooper and A. Li. Vol. 7287 of Lect. Notes Comput. Sci. Springer-Verlag (2012) 202–213. | MR | Zbl

U. Feige and M. Langberg, Approximation algorithms for maximization problems arising in graph partitioning. J. Algorithms 41 (2001) 174–211. | DOI | MR | Zbl

M.R. Fellows, A. Kulik, F.A. Rosamond and H. Shachnai, Parameterized approximation via fidelity preserving transformations. In Proc. of ICALP’12, edited by A. Czumaj, K. Mehlhorn, A. Pitts and R. Wattenhofer. Vol. 7391 of Lect. Notes Comput. Sci. Springer-Verlag (2012) 351–362. | Zbl

F.V. Fomin and D. Kratsch, Exact exponential algorithms. EATCS. Springer-Verlag (2010). | MR

F.V. Fomin and Y. Villanger, Finding induced subgraphs via minimal triangulations. In Proc. of International Symposium on Theoretical Aspects of Computer Science, STACS’10, edited by J.-Y. Marion and T. Schwentick. Nancy, France (2010) 383–394. | MR | Zbl

F.V. Fomin, F. Grandoni and D. Kratsch, A measure & conquer approach for the analysis of exact algorithms. J. Assoc. Comput. Mach. 56 (2009) 1–32. | DOI | MR | Zbl

M. Fürer, S. Gaspers and S.P. Kasiviswanathan, An exponential time 2-approximation algorithm for bandwidth. In Proc. of International Workshop on Parameterized and Exact Computation, IWPEC’09. Vol. 5917 of Lect. Notes Comput. Sci. Springer (2009). | MR | Zbl

M.R. Garey and D.S. Johnson, Computers and intractability. A guide to the theory of NP-completeness. W. H. Freeman, San Francisco (1979). | MR | Zbl

M.X. Goemans and D.P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. Assoc. Comput. Mach. 42 (1995) 1115–1145. | DOI | MR | Zbl

J. Håstad, Some optimal inapproximability results. J. Assoc. Comput. Mach. 48 (2001) 798–859. | DOI | MR | Zbl

R. Impagliazzo and R. Paturi, On the complexity of $k$-sat. J. Comput. System Sci. 62 (2001) 367–375. | DOI | MR | Zbl

R. Impagliazzo, R. Paturi and F. Zane, Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63 (2001) 512–530. | DOI | MR | Zbl

G. Jäger and A. Srivastav, Improved approximation algorithms for maximum graph partitioning problems. J. Comb. Optim. 10 (2005) 133–167. | DOI | MR | Zbl

R.M. Karp, Reducibility among combinatorial problems. Complexity of computer computations, edited by R.E. Miller and J.W. Thatcher. Plenum Press, New York (1972) 85–103. | MR | Zbl

D. Marx, Parameterized complexity and approximation algorithms. Comput. J. 51 (2008) 60–78. | DOI

C.H. Papadimitriou and M. Yannakakis, Optimization, approximation and complexity classes. J. Comput. Syst. Sci. 43 (1991) 425–440. | DOI | MR | Zbl

I. Razgon, Computing minimum directed feedback vertex set in $o(1.{9977}^n)$. In Proc. of Italian Conference in Theoretical Computer Science, ICTCS’07, edited by G.F. Italiano, E. Moggi and L. Laura. World Scientific (2007) 70–81.