{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,29]],"date-time":"2026-09-29T06:03:45Z","timestamp":1790661825242,"version":"4.1.0"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T00:00:00Z","timestamp":1787011200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T00:00:00Z","timestamp":1787011200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100019180","name":"HORIZON EUROPE European Research Council","doi-asserted-by":"publisher","award":["852780"],"award-info":[{"award-number":["852780"]}],"id":[{"id":"10.13039\/100019180","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["725978"],"award-info":[{"award-number":["725978"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2026,10]]},"abstract":"Abstract<\/jats:title>\n \n In a recent work, Esmer et al. describe a simple method \u2013 approximate monotone local search \u2013 to obtain exponential approximation algorithms from existing parameterized exact algorithms, polynomial-time approximation algorithms and, more generally, parameterized approximation algorithms. In this work, we generalize those results to the weighted setting. More formally, we consider monotone subset minimization problems over a weighted universe of size\n n<\/jats:italic>\n (e.g.,\n Vertex Cover<\/jats:sc>\n ,\n d<\/jats:italic>\n -Hitting Set<\/jats:sc>\n and\n Feedback Vertex Set<\/jats:sc>\n ). We consider a model where the algorithm is only given access to a subroutine that finds a solution of weight at most\n \n \n $$\\alpha \\cdot W$$<\/jats:tex-math>\n \n \n \u03b1<\/mml:mi>\n \u00b7<\/mml:mo>\n W<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n (and of arbitrary cardinality) in time\n \n \n $$c^k \\cdot n^{\\mathcal {O}(1)}$$<\/jats:tex-math>\n \n \n \n c<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msup>\n \u00b7<\/mml:mo>\n \n n<\/mml:mi>\n \n O<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n where\u00a0\n W<\/jats:italic>\n is the minimum weight of a solution of cardinality at most\n k<\/jats:italic>\n . In the unweighted setting, Esmer et al. determine the smallest value\n d<\/jats:italic>\n for which a\n \n \n $$\\beta $$<\/jats:tex-math>\n \n \u03b2<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -approximation algorithm running in time\n \n \n $$d^{n + o(n)}$$<\/jats:tex-math>\n \n \n d<\/mml:mi>\n \n n<\/mml:mi>\n +<\/mml:mo>\n o<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n can be obtained in this model. We show that the same dependencies also hold in a weighted setting in this model: we obtain a\n \n \n $$\\beta $$<\/jats:tex-math>\n \n \u03b2<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -approximation algorithm running in time\n \n \n $$d^{n + o(n)}$$<\/jats:tex-math>\n \n \n d<\/mml:mi>\n \n n<\/mml:mi>\n +<\/mml:mo>\n o<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , for the same\n d<\/jats:italic>\n as in the unweighted setting. Similarly, we also extend a\n \n \n $$\\beta $$<\/jats:tex-math>\n \n \u03b2<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -approximate brute-force search (in a model which only provides access to a membership oracle) to the weighted setting. Using existing approximation algorithms and exact parameterized algorithms for weighted problems, we obtain the first exponential-time\n \n \n $$\\beta $$<\/jats:tex-math>\n \n \u03b2<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -approximation algorithms that are better than brute force for a variety of problems including\n Weighted Vertex Cover<\/jats:sc>\n ,\n Weighted<\/jats:sc>\n d<\/jats:italic>\n -Hitting Set<\/jats:sc>\n ,\n Weighted Feedback Vertex Set<\/jats:sc>\n and\n Weighted Multicut<\/jats:sc>\n .\n <\/jats:p>","DOI":"10.1007\/s00453-026-01402-7","type":"journal-article","created":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T04:07:08Z","timestamp":1787026028000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Approximate Monotone Local Search for Weighted Problems"],"prefix":"10.1007","volume":"88","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5694-1465","authenticated-orcid":false,"given":"Bar\u0131\u015f Can","family":"Esmer","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0533-3926","authenticated-orcid":false,"given":"Ariel","family":"Kulik","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"D\u00e1niel","family":"Marx","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4940-0318","authenticated-orcid":false,"given":"Daniel","family":"Neuen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Roohani","family":"Sharma","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,8,18]]},"reference":[{"key":"1402_CR1","doi-asserted-by":"publisher","unstructured":"Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-16533-7","DOI":"10.1007\/978-3-642-16533-7"},{"issue":"2","key":"1402_CR2","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1016\/0196-6774(81)90020-1","volume":"2","author":"R Bar-Yehuda","year":"1981","unstructured":"Bar-Yehuda, R., Even, S.: A linear-time approximation algorithm for the weighted vertex cover problem. J. Algorithms 2(2), 198\u2013203 (1981). https:\/\/doi.org\/10.1016\/0196-6774(81)90020-1","journal-title":"J. Algorithms"},{"key":"1402_CR3","doi-asserted-by":"publisher","unstructured":"Esmer, B.C., Kulik, A., Marx, D., Neuen, D., Sharma, R.: Optimally repurposing existing algorithms to obtain exponential-time approximations. In: Woodruff, D.P. (ed.) Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024, pp. 314\u2013345. SIAM, Alexandria, VA, USA (2024). https:\/\/doi.org\/10.1137\/1.9781611977912.13","DOI":"10.1137\/1.9781611977912.13"},{"key":"1402_CR4","doi-asserted-by":"publisher","unstructured":"Esmer, B.C., Kulik, A., Marx, D., Neuen, D., Sharma, R.: Faster exponential-time approximation algorithms using approximate monotone local search. In: Chechik, S., Navarro, G., Rotenberg, E., Herman, G. (eds.) 30th Annual European Symposium on Algorithms, ESA 2022, September 5-9, 2022, Berlin\/Potsdam, Germany. LIPIcs, vol. 244, pp. 50\u201315019. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2022). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2022.50","DOI":"10.4230\/LIPIcs.ESA.2022.50"},{"issue":"5","key":"1402_CR5","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1145\/2775105","volume":"62","author":"S Arora","year":"2015","unstructured":"Arora, S., Barak, B., Steurer, D.: Subexponential algorithms for unique games and related problems. J. ACM 62(5), 42\u201314225 (2015). https:\/\/doi.org\/10.1145\/2775105","journal-title":"J. ACM"},{"issue":"10","key":"1402_CR6","doi-asserted-by":"publisher","first-page":"3993","DOI":"10.1007\/s00453-018-0512-8","volume":"81","author":"N Bansal","year":"2019","unstructured":"Bansal, N., Chalermsook, P., Laekhanukit, B., Nanongkai, D., Nederlof, J.: New tools and connections for exponential-time approximation. Algorithmica 81(10), 3993\u20134009 (2019). https:\/\/doi.org\/10.1007\/s00453-018-0512-8","journal-title":"Algorithmica"},{"issue":"17","key":"1402_CR7","doi-asserted-by":"publisher","first-page":"1954","DOI":"10.1016\/j.dam.2011.07.009","volume":"159","author":"N Bourgeois","year":"2011","unstructured":"Bourgeois, N., Escoffier, B., Paschos, V.T.: Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms. Discret. Appl. Math. 159(17), 1954\u20131970 (2011). https:\/\/doi.org\/10.1016\/j.dam.2011.07.009","journal-title":"Discret. Appl. Math."},{"issue":"16","key":"1402_CR8","doi-asserted-by":"publisher","first-page":"957","DOI":"10.1016\/j.ipl.2009.05.003","volume":"109","author":"M Cygan","year":"2009","unstructured":"Cygan, M., Kowalik, L., Wykurz, M.: Exponential-time approximation of weighted set cover. Inf. Process. Lett. 109(16), 957\u2013961 (2009). https:\/\/doi.org\/10.1016\/j.ipl.2009.05.003","journal-title":"Inf. Process. Lett."},{"issue":"4\u20135","key":"1402_CR9","doi-asserted-by":"publisher","first-page":"979","DOI":"10.1051\/ro\/2015060","volume":"50","author":"B Escoffier","year":"2016","unstructured":"Escoffier, B., Paschos, V.T., Tourniaire, E.: Super-polynomial approximation branching algorithms. RAIRO Oper. Res. 50(4\u20135), 979\u2013994 (2016). https:\/\/doi.org\/10.1051\/ro\/2015060","journal-title":"RAIRO Oper. Res."},{"key":"1402_CR10","doi-asserted-by":"publisher","unstructured":"Manurangsi, P., Trevisan, L.: Mildly exponential time approximation algorithms for vertex cover, balanced separator and uniform sparsest cut. In: Blais, E., Jansen, K., Rolim, J.D.P., Steurer, D. (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2018, August 20-22, 2018 - Princeton, NJ, USA. LIPIcs, vol. 116, pp. 20\u201312017. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2018). https:\/\/doi.org\/10.4230\/LIPIcs.APPROX-RANDOM.2018.20","DOI":"10.4230\/LIPIcs.APPROX-RANDOM.2018.20"},{"issue":"2","key":"1402_CR11","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1145\/3284176","volume":"66","author":"FV Fomin","year":"2019","unstructured":"Fomin, F.V., Gaspers, S., Lokshtanov, D., Saurabh, S.: Exact algorithms via monotone local search. J. ACM 66(2), 8\u20131823 (2019). https:\/\/doi.org\/10.1145\/3284176","journal-title":"J. ACM"},{"issue":"3","key":"1402_CR12","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1137\/S0895480196305124","volume":"12","author":"V Bafna","year":"1999","unstructured":"Bafna, V., Berman, P., Fujito, T.: A 2-approximation algorithm for the undirected feedback vertex set problem. SIAM J. Discret. Math. 12(3), 289\u2013297 (1999). https:\/\/doi.org\/10.1137\/S0895480196305124","journal-title":"SIAM J. Discret. Math."},{"key":"1402_CR13","doi-asserted-by":"publisher","unstructured":"Shachnai, H., Zehavi, M.: A multivariate framework for weighted FPT algorithms. J. Comput. Syst. Sci. 89, 157\u2013189 (2017). https:\/\/doi.org\/10.1016\/j.jcss.2017.05.003","DOI":"10.1016\/j.jcss.2017.05.003"},{"issue":"7\u20139","key":"1402_CR14","doi-asserted-by":"publisher","first-page":"1045","DOI":"10.1016\/j.tcs.2009.11.012","volume":"411","author":"FV Fomin","year":"2010","unstructured":"Fomin, F.V., Gaspers, S., Kratsch, D., Liedloff, M., Saurabh, S.: Iterative compression and exact algorithms. Theor. Comput. Sci. 411(7\u20139), 1045\u20131053 (2010). https:\/\/doi.org\/10.1016\/j.tcs.2009.11.012","journal-title":"Theor. Comput. Sci."},{"key":"1402_CR15","doi-asserted-by":"publisher","unstructured":"Agrawal, A., Kolay, S., Lokshtanov, D., Saurabh, S.: A faster FPT algorithm and a smaller kernel for block graph vertex deletion. In: Kranakis, E., Navarro, G., Ch\u00e1vez, E. (eds.) LATIN 2016: Theoretical Informatics - 12th Latin American Symposium, Ensenada, Mexico, April 11-15, 2016, Proceedings. Lecture Notes in Computer Science, vol. 9644, pp. 1\u201313. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-662-49529-2_1","DOI":"10.1007\/978-3-662-49529-2_1"},{"key":"1402_CR16","doi-asserted-by":"publisher","unstructured":"Lokshtanov, D., Misra, P., Ramanujan, M.S., Saurabh, S., Zehavi, M.: FPT-approximation for FPT problems. In: Marx, D. (ed.) Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pp. 199\u2013218. SIAM, Philadelphia, PA, USA (2021). https:\/\/doi.org\/10.1137\/1.9781611976465.14","DOI":"10.1137\/1.9781611976465.14"},{"issue":"2","key":"1402_CR17","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/S0196-6774(03)00005-1","volume":"47","author":"R Niedermeier","year":"2003","unstructured":"Niedermeier, R., Rossmanith, P.: On efficient fixed-parameter algorithms for weighted vertex cover. J. Algorithms 47(2), 63\u201377 (2003). https:\/\/doi.org\/10.1016\/S0196-6774(03)00005-1","journal-title":"J. Algorithms"},{"key":"1402_CR18","doi-asserted-by":"publisher","unstructured":"Wahlstr\u00f6m, M.: A tighter bound for counting max-weight solutions to 2sat instances. In: Grohe, M., Niedermeier, R. (eds.) Parameterized and Exact Computation, Third International Workshop, IWPEC 2008, Victoria, Canada, May 14-16, 2008. Proceedings. Lecture Notes in Computer Science, vol. 5018, pp. 202\u2013213. Springer, Berlin, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-79723-4_19","DOI":"10.1007\/978-3-540-79723-4_19"},{"key":"1402_CR19","doi-asserted-by":"publisher","unstructured":"Mandal, S., Misra, P., Rai, A., Saurabh, S.: Parameterized approximation algorithms for weighted vertex cover. Theor. Comput. Sci. 1021, 114870 (2024). https:\/\/doi.org\/10.1016\/J.TCS.2024.114870","DOI":"10.1016\/J.TCS.2024.114870"},{"issue":"4","key":"1402_CR20","doi-asserted-by":"publisher","first-page":"1231","DOI":"10.1137\/S0097539798340047","volume":"30","author":"G Even","year":"2000","unstructured":"Even, G., Naor, J., Zosin, L.: An 8-approximation algorithm for the subset feedback vertex set problem. SIAM J. Comput. 30(4), 1231\u20131252 (2000). https:\/\/doi.org\/10.1137\/S0097539798340047","journal-title":"SIAM J. Comput."},{"key":"1402_CR21","doi-asserted-by":"publisher","unstructured":"Bshouty, N.H., Burroughs, L.: Massaging a linear programming solution to give a 2-approximation for a generalization of the vertex cover problem. In: Morvan, M., Meinel, C., Krob, D. (eds.) STACS 98, 15th Annual Symposium on Theoretical Aspects of Computer Science, Paris, France, February 25-27, 1998, Proceedings. Lecture Notes in Computer Science, vol. 1373, pp. 298\u2013308. Springer, Berlin, Heidelberg (1998). https:\/\/doi.org\/10.1007\/BFb0028569","DOI":"10.1007\/BFb0028569"},{"key":"1402_CR22","doi-asserted-by":"publisher","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3","DOI":"10.1007\/978-3-319-21275-3"},{"key":"1402_CR23","unstructured":"Still, G.: Lectures on parametric optimization: An introduction. Optimization Online, (2018)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-026-01402-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-026-01402-7","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-026-01402-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,9,29]],"date-time":"2026-09-29T05:33:16Z","timestamp":1790659996000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-026-01402-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,8,18]]},"references-count":23,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2026,10]]}},"alternative-id":["1402"],"URL":"https:\/\/doi.org\/10.1007\/s00453-026-01402-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,8,18]]},"assertion":[{"value":"29 April 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 July 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 August 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors have no financial or proprietary interests in any material discussed in this article. This paper has been selected as one of the five top papers at IPEC 2023.","order":1,"name":"Ethics","label":"Conflict of Interest","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","label":"Competing interests","group":{"name":"EthicsHeading","label":"Declarations"}}],"article-number":"59"}}