Super-polynomial approximation branching algorithms. (English) Zbl 1401.68360
Summary: We give sufficient conditions for deriving moderately exponential and/or parameterized time approximation schemata (i.e., algorithms achieving ratios \(1\pm \epsilon\), for arbitrarily small \(\epsilon\)) for broad classes of combinatorial optimization problems via a well-known technique widely used for deriving exact algorithms, namely the branching tree pruning.
MSC:
| 68W25 | Approximation algorithms |
| 68Q25 | Analysis of algorithms and problem complexity |
| 90C27 | Combinatorial optimization |
References:
| [1] | 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). · Zbl 0937.68002 |
| [2] | 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:10.1016/0004-3702(95)00004-6 |
| [3] | 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. · Zbl 1309.68229 |
| [4] | N. Bourgeois, B. Escoffier and V. Th. Paschos, Efficient approximation of min coloring by moderately exponential algorithms. Inform. Process. Lett.109 (2009) 950-954. · Zbl 1197.05141 · doi:10.1016/j.ipl.2009.05.002 |
| [5] | 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. · Zbl 1237.05146 · doi:10.1016/j.dam.2011.07.009 |
| [6] | 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. · Zbl 1310.68235 |
| [7] | 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. · Zbl 1154.68570 |
| [8] | 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. · Zbl 1154.68571 |
| [9] | F. Della Croce and V.Th. Paschos, Efficient algorithms for the max k-vertex cover problem. J. Comb. Optim.28 (2014) 674-691. · Zbl 1315.90056 · doi:10.1007/s10878-012-9575-7 |
| [10] | M. Cygan and M. Pilipczuk, Exact and approximate bandwidth. Theoret. Comput. Sci.411 (2010) 3701-3713. · Zbl 1207.68443 · doi:10.1016/j.tcs.2010.06.018 |
| [11] | E. Dantsin, M. Gavrilovich, E.A. Hirsch and B. Konev, max sat approximation beyond the limits of polynomial-time approximation. Ann. Pure Appl. Logic113 (2002) 81-94. · Zbl 0990.03006 · doi:10.1016/S0168-0072(01)00052-5 |
| [12] | 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. · Zbl 1163.90767 · doi:10.1016/j.orl.2006.04.001 |
| [13] | I. Dinur and M. Safra, The importance of being biased. In Proc. of STOC’02 (2002) 33-42. · Zbl 1192.68318 |
| [14] | R.G. Downey and M.R. Fellows, Parameterized complexity. Monogr. Comput. Sci. Springer, New York (1999). |
| [15] | 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. · Zbl 1154.68572 |
| [16] | 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. · Zbl 1354.68298 |
| [17] | U. Feige and M. Langberg, Approximation algorithms for maximization problems arising in graph partitioning. J. Algorithms41 (2001) 174-211. · Zbl 1017.68086 · doi:10.1006/jagm.2001.1183 |
| [18] | 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 1272.68459 |
| [19] | F.V. Fomin and D. Kratsch, Exact exponential algorithms. EATCS. Springer-Verlag (2010). · Zbl 1370.68002 |
| [20] | 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. · Zbl 1230.68108 |
| [21] | 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. · Zbl 1325.68311 · doi:10.1145/1552285.1552286 |
| [22] | 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). · Zbl 1273.68408 |
| [23] | M.R. Garey and D.S. Johnson, Computers and intractability. A guide to the theory of NP-completeness. W. H. Freeman, San Francisco (1979). · Zbl 0411.68039 |
| [24] | 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. · Zbl 0885.68088 · doi:10.1145/227683.227684 |
| [25] | J. Håstad, Some optimal inapproximability results. J. Assoc. Comput. Mach.48 (2001) 798-859. · Zbl 1127.68405 · doi:10.1145/502090.502098 |
| [26] | R. Impagliazzo and R. Paturi, On the complexity of k-sat. J. Comput. System Sci.62 (2001) 367-375. · Zbl 0990.68079 · doi:10.1006/jcss.2000.1727 |
| [27] | R. Impagliazzo, R. Paturi and F. Zane, Which problems have strongly exponential complexity? J. Comput. Syst. Sci.63 (2001) 512-530. · Zbl 1006.68052 · doi:10.1006/jcss.2001.1774 |
| [28] | G. Jäger and A. Srivastav, Improved approximation algorithms for maximum graph partitioning problems. J. Comb. Optim.10 (2005) 133-167. · Zbl 1093.90069 · doi:10.1007/s10878-005-2269-7 |
| [29] | 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. |
| [30] | D. Marx, Parameterized complexity and approximation algorithms. Comput. J.51 (2008) 60-78. · doi:10.1093/comjnl/bxm048 |
| [31] | C.H. Papadimitriou and M. Yannakakis, Optimization, approximation and complexity classes. J. Comput. Syst. Sci.43 (1991) 425-440. · Zbl 0765.68036 · doi:10.1016/0022-0000(91)90023-X |
| [32] | 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. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
