Super-polynomial approximation branching algorithms
RAIRO - Operations Research - Recherche Opérationnelle, Special issue - Advanced Optimization Approaches and Modern OR-Applications, 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±ϵ, 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.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2015060
Classification : 68W25, 05C85, 68Q25
Mots-clés : Branching algorithm, moderately exponential approximation, approximation schema
Escoffier, Bruno 1 ; Paschos, Vangelis Th. 2 ; Tourniaire, Emeric 2

1 Sorbonne Universités, UPMC Univ Paris 06, CNRS, LIP6 UMR 7606, 4 place Jussieu, 75005 Paris, France.
2 PSL Research University, Université Paris-Dauphine, LAMSADE CNRS UMR 7243, Paris, France.
@article{RO_2016__50_4-5_979_0,
     author = {Escoffier, Bruno and Paschos, Vangelis Th. and Tourniaire, Emeric},
     title = {Super-polynomial approximation branching algorithms},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {979--994},
     publisher = {EDP-Sciences},
     volume = {50},
     number = {4-5},
     year = {2016},
     doi = {10.1051/ro/2015060},
     mrnumber = {3570543},
     zbl = {1401.68360},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2015060/}
}
TY  - JOUR
AU  - Escoffier, Bruno
AU  - Paschos, Vangelis Th.
AU  - Tourniaire, Emeric
TI  - Super-polynomial approximation branching algorithms
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2016
SP  - 979
EP  - 994
VL  - 50
IS  - 4-5
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2015060/
DO  - 10.1051/ro/2015060
LA  - en
ID  - RO_2016__50_4-5_979_0
ER  - 
%0 Journal Article
%A Escoffier, Bruno
%A Paschos, Vangelis Th.
%A Tourniaire, Emeric
%T Super-polynomial approximation branching algorithms
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2016
%P 979-994
%V 50
%N 4-5
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2015060/
%R 10.1051/ro/2015060
%G en
%F RO_2016__50_4-5_979_0
Escoffier, Bruno; Paschos, Vangelis Th.; Tourniaire, Emeric. Super-polynomial approximation branching algorithms. RAIRO - Operations Research - Recherche Opérationnelle, Special issue - Advanced Optimization Approaches and Modern OR-Applications, Tome 50 (2016) no. 4-5, pp. 979-994. doi : 10.1051/ro/2015060. http://www.numdam.org/articles/10.1051/ro/2015060/

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.

Cité par Sources :