×

zbMATH — the first resource for mathematics

Local search: is brute-force avoidable? (English) Zbl 1244.68070
Summary: Many local search algorithms are based on searching in the \(k\)-exchange neighborhood. This is the set of solutions that can be obtained from the current solution by exchanging at most \(k\) elements. As a rule of thumb, the larger \(k\) is, the better are the chances of finding an improved solution. However, for inputs of size \(n\), a naïve brute-force search of the \(k\)-exchange neighborhood requires \(n^{O(k)}\) time, which is not practical even for very small values of \(k\). We show that for several classes of sparse graphs, including planar graphs, graphs of bounded vertex degree and graphs excluding some fixed graph as a minor, an improved solution in the \(k\)-exchange neighborhood for many problems can be found much more efficiently. Our algorithms run in time \(\mathcal O(\tau (k)\cdot n^c\)), where \(\tau \) is a function depending only on \(k\) and \(c\) is a constant independent of \(k\) and \(n\). We demonstrate the applicability of this approach on a variety of problems including \(r\)-Center, Vertex Cover, Odd Cycle Transversal, Max-Cut, and Min-Bisection. In particular, on planar graphs, all our algorithms searching for a \(k\)-local improvement run in time \(\mathcal O(2^{\mathcal O(k)}\cdot n^{2})\), which is polynomial for \(k=\mathcal O(\log n)\). We complement these fixed-parameter tractable algorithms for \(k\)-local search with parameterized intractability results indicating that brute-force search is unavoidable in more general classes of graphs.

MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
05C85 Graph algorithms (graph-theoretic aspects)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aarts, E.H.L.; Korst, J.; van Laarhoven, P.J.M., Simulated annealing, (), 91-120 · Zbl 0905.90140
[2] Aarts, E.H.L.; Lenstra, J.K., Local search in combinatorial optimization, (1997), Princeton University Press
[3] F. Bock, An algorithm for solving ‘traveling-salesman’ and related network optimization problems, Research report, Armour Research Foundation, 1958.
[4] Bodlaender, H.L., A partial k-arboretum of graphs with bounded treewidth, Theoret. comput. sci., 209, 1-45, (1998) · Zbl 0912.68148
[5] Chen, J.; Kanj, I.A.; Xia, G., Improved upper bounds for vertex cover, Theoret. comput. sci., 411, 3736-3756, (2010) · Zbl 1205.05217
[6] Croes, G., A method for solving traveling-salesman problems, Oper. res., 6, 791-812, (1958)
[7] Demaine, E.D.; Fomin, F.V.; Hajiaghayi, M.T.; Thilikos, D.M., Fixed-parameter algorithms for (\(k, r\))-center in planar graphs and map graphs, ACM trans. algorithms, 1, 33-47, (2005) · Zbl 1321.05256
[8] Demaine, E.D.; Fomin, F.V.; Hajiaghayi, M.T.; Thilikos, D.M., Subexponential parameterized algorithms on bounded-genus graphs and minor-free graphs, J. ACM, 52, 866-893, (2005) · Zbl 1326.05152
[9] Demaine, E.D.; Hajiaghayi, M., Linearity of grid minors in treewidth with applications through bidimensionality, Combinatorica, 28, 19-36, (2008) · Zbl 1174.05115
[10] E.D. Demaine, M.T. Hajiaghayi, K. ichi Kawarabayashi, Algorithmic graph minor theory: Decomposition, approximation, and coloring, in: FOCS, 2005, pp. 637-646.
[11] Downey, R.G.; Fellows, M.R., Parameterized complexity, (1999), Springer-Verlag New York · Zbl 0914.68076
[12] Eppstein, D., Diameter and treewidth in minor-closed graph families, Algorithmica, 27, 275-291, (2000) · Zbl 0963.05128
[13] Faigle, U.; Kern, W., Note on the convergence of simulated annealing algorithms, SIAM J. control optim., 29, 153-159, (1991) · Zbl 0736.90061
[14] Feige, U.; Hajiaghayi, M.; Lee, J.R., Improved approximation algorithms for minimum weight vertex separators, SIAM J. comput., 38, 629-657, (2008) · Zbl 1172.68063
[15] M. Fellows, F.V. Fomin, D. Lokshtanov, F. Rosamond, S. Saurabh, Y. Villanger, Local search: Is brute-force avoidable?, in: Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI-09), AAAI, 2009, pp. 486-491. · Zbl 1244.68070
[16] Flum, J.; Grohe, M., Parameterized complexity theory, (2006), Springer-Verlag Berlin
[17] Fomin, F.V.; Lokshtanov, D.; Raman, V.; Saurabh, S., Fast local search algorithm for weighted feedback arc set in tournaments, (), 65-70
[18] Grohe, M., Local tree-width, excluded minors, and approximation algorithms, Combinatorica, 23, 613-632, (2003) · Zbl 1089.05503
[19] A. Gupta, É. Tardos, A constant factor approximation algorithm for a class of classification problems, in: STOC, 2000, pp. 652-658. · Zbl 1296.68078
[20] Jansen, K.; Karpinski, M.; Lingas, A.; Seidel, E., Polynomial time approximation schemes for MAX-bisection on planar and geometric graphs, SIAM J. comput., 35, 110-119, (2005) · Zbl 1087.90063
[21] Johnson, D.S.; Papadimitriou, C.H.; Yannakakis, M., How easy is local search?, J. comput. syst. sci., 37, 79-100, (1988) · Zbl 0655.68074
[22] Khanna, S.; Motwani, R.; Sudan, M.; Vazirani, U.V., On syntactic versus computational views of approximability, SIAM J. comput., 28, 164-191, (1998) · Zbl 0915.68068
[23] Khot, S.; Raman, V., Parameterized complexity of finding subgraphs with hereditary properties, Theoret. comput. sci., 289, 997-1008, (2002) · Zbl 1061.68061
[24] Khuller, S.; Bhatia, R.; Pless, R., On local search and placement of meters in networks, SIAM J. comput., 32, 470-487, (2003) · Zbl 1033.90107
[25] Kleinberg, J.; Tardos, E., Algorithm design, (2005), Addison-Wesley Longman Publishing Co., Inc. Boston, MA, USA
[26] Krokhin, A.; Marx, D., On the hardness of losing weight, (), 662-673 · Zbl 1153.68382
[27] Lin, S.; Kernighan, B.W., An effective heuristic algorithm for traveling-salesman problem, Oper. res., 21, 498-516, (1973) · Zbl 0256.90038
[28] Marx, D., Local search, Parameterized complexity newsletter, 3, 7-8, (2008)
[29] Marx, D., Searching the k-change neighborhood for TSP is \(W [1]\)-hard, Oper. res. lett., 36, 31-36, (2008) · Zbl 1166.90364
[30] Michiels, W.; Aarts, E.H.L.; Korst, J., Theoretical aspects of local search, (2007), Springer-Verlag · Zbl 1130.90061
[31] Niedermeier, R., Invitation to fixed-parameter algorithms, (2006), Oxford University Press · Zbl 1095.68038
[32] Papadimitriou, C.H.; Steiglitz, K., On the complexity of local search for the traveling salesman problem, SIAM J. comput., 6, 76-83, (1977) · Zbl 0381.68043
[33] Papadimitriou, C.H.; Steiglitz, K., Combinatorial optimization: algorithms and complexity, (1982), Prentice Hall · Zbl 0503.90060
[34] Robertson, N.; Seymour, P.D., Graph minors V. excluding a planar graph, J. combin. theory ser. B, 41, 92-114, (1986) · Zbl 0598.05055
[35] Robertson, N.; Seymour, P.D., Graph minors X. obstructions to tree-decomposition, J. combin. theory ser. B, 52, 153-190, (1991) · Zbl 0764.05069
[36] Robertson, N.; Seymour, P.D., Graph minors XVI. excluding a non-planar graph, J. combin. theory ser. B, 89, 43-76, (2003) · Zbl 1023.05040
[37] Szeider, S., The parameterized complexity of k-flip local search for sat and MAX sat, Discrete optim., 8, 139-145, (2011) · Zbl 1248.90067
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.