Abstract
We address the problem of whether the brute-force procedure for the local improvement step in a local search algorithm can be substantially improved when applied to classical NP-hard string problems. We examine four problems in this domain: Closest String, Longest Common Subsequence, Shortest Common Supersequence, and Shortest Common Superstring. Herein, we consider arguably the most fundamental string distance measure, namely the Hamming distance, which has been applied in practical local search implementations for string problems. Our results indicate that for all four problems, the brute-force algorithm is essentially optimal.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aarts, E.H.L., Lenstra, J.K.: Local Search in Combinatorial Optimization. Wiley-Interscience (1997)
Balas, E.: New classes of efficiently solvable generalized traveling salesman problems. Ann. Oper. Res. 86, 529–558 (1999)
Chen, J., Chor, B., Fellows, M., Huang, X., Juedes, D.W., Kanj, I.A., Xia, G.: Tight lower bounds for certain parameterized NP-hard problems. Inform. Comput. 201(2), 216–231 (2005)
Dörnfelder, M., Guo, J., Komusiewicz, C., Weller, M.: On the parameterized complexity of consensus clustering. In: Asano, T., Nakano, S.-I., Okamoto, Y., Watanabe, O. (eds.) ISAAC 2011. LNCS, vol. 7074, pp. 624–633. Springer, Heidelberg (2011)
Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer (1999)
Fellows, M.R., Rosamond, F.A., Fomin, F.V., Lokshtanov, D., Saurabh, S., Villanger, Y.: Local search: Is brute-force avoidable? J. Comput. Syst. Sci. 78(3), 707–719 (2012)
Festa, P., Pardalos, P.M.: Efficient solutions for the far from most string problem. Ann. Oper. Res. 196(1), 663–682 (2012)
Fomin, F.V., Lokshtanov, D., Raman, V., Saurabh, S.: Fast local search algorithm for weighted feedback arc set in tournaments. In: Proc. 24th AAAI. AAAI Press (2010)
Gramm, J., Niedermeier, R., Rossmanith, P.: Fixed-parameter algorithms for closest string and related problems. Algorithmica 37(1), 25–42 (2003)
Guo, J., Hartung, S., Niedermeier, R., Suchý, O.: The parameterized complexity of local search for TSP, more refined. In: Asano, T., Nakano, S.-I., Okamoto, Y., Watanabe, O. (eds.) ISAAC 2011. LNCS, vol. 7074, pp. 614–623. Springer, Heidelberg (2011)
Johnson, D.S., Papadimitriou, C.H., Yannakakis, M.: How easy is local search? J. Comput. Syst. Sci. 37(1), 79–100 (1988)
Krokhin, A., Marx, D.: On the hardness of losing weight. ACM T. Alg. 8(2), 19 (2012)
Marx, D.: Searching the k-change neighborhood for TSP is W[1]-hard. Oper. Res. Lett. 36(1), 31–36 (2008)
Marx, D., Schlotter, I.: Stable assignment with couples: Parameterized complexity and local search. Discr. Optim. 8(1), 25–40 (2011)
Meneses, C., Oliveira, C.A.S., Pardalos, P.M.: Optimization techniques for string selection and comparison problems in genomics. IEEE Eng. Med. Bio. Mag. 24(3), 81–87 (2005)
Szeider, S.: The parameterized complexity of k-flip local search for SAT and MAX SAT. Discr. Optim. 8(1), 139–145 (2011)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Guo, J., Hermelin, D., Komusiewicz, C. (2013). Local Search for String Problems: Brute Force Is Essentially Optimal. In: Fischer, J., Sanders, P. (eds) Combinatorial Pattern Matching. CPM 2013. Lecture Notes in Computer Science, vol 7922. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38905-4_14
Download citation
DOI: https://doi.org/10.1007/978-3-642-38905-4_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-38904-7
Online ISBN: 978-3-642-38905-4
eBook Packages: Computer ScienceComputer Science (R0)