We give sufficient conditions for deriving moderately exponential and/or parameterized time approximation schemata (, algorithms achieving ratios , 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.
Accepté le :
DOI : 10.1051/ro/2015060
Keywords: Branching algorithm, moderately exponential approximation, approximation schema
Escoffier, Bruno 1 ; Paschos, Vangelis Th. 2 ; Tourniaire, Emeric 2
@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},
year = {2016},
publisher = {EDP Sciences},
volume = {50},
number = {4-5},
doi = {10.1051/ro/2015060},
mrnumber = {3570543},
zbl = {1401.68360},
language = {en},
url = {https://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 - https://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 https://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
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
and , Optimization of pearl’s method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem. Artif. Intell. 83 (1996) 167–188. | MR | Zbl | DOI
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
, and , Efficient approximation of min coloring by moderately exponential algorithms. Inform. Process. Lett. 109 (2009) 950–954. | MR | Zbl | DOI
, and . Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms. Discrete Appl. Math. 159 (2011) 1954–1970. | MR | Zbl | DOI
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
and , Efficient algorithms for the max -vertex cover problem. J. Comb. Optim. 28 (2014) 674–691. | MR | Zbl | DOI
and , Exact and approximate bandwidth. Theoret. Comput. Sci. 411 (2010) 3701–3713. | MR | Zbl | DOI
, , and , max sat approximation beyond the limits of polynomial-time approximation. Ann. Pure Appl. Logic 113 (2002) 81–94. | MR | Zbl | DOI
, and , An exact algorithm for max cut in sparse graphs. Oper. Res. Lett. 35 (2007) 403–408. | MR | Zbl | DOI
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
and , Approximation algorithms for maximization problems arising in graph partitioning. J. Algorithms 41 (2001) 174–211. | MR | Zbl | DOI
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
, and , A measure & conquer approach for the analysis of exact algorithms. J. Assoc. Comput. Mach. 56 (2009) 1–32. | MR | Zbl | DOI
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
and , Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. Assoc. Comput. Mach. 42 (1995) 1115–1145. | MR | Zbl | DOI
, Some optimal inapproximability results. J. Assoc. Comput. Mach. 48 (2001) 798–859. | MR | Zbl | DOI
and , On the complexity of -sat. J. Comput. System Sci. 62 (2001) 367–375. | MR | Zbl | DOI
, and , Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63 (2001) 512–530. | MR | Zbl | DOI
and , Improved approximation algorithms for maximum graph partitioning problems. J. Comb. Optim. 10 (2005) 133–167. | MR | Zbl | DOI
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
, Parameterized complexity and approximation algorithms. Comput. J. 51 (2008) 60–78. | DOI
and , Optimization, approximation and complexity classes. J. Comput. Syst. Sci. 43 (1991) 425–440. | MR | Zbl | DOI
I. Razgon, Computing minimum directed feedback vertex set in . 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 :
