{"ID":2823305,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2601.00768","arxiv_id":"2601.00768","title":"Mind the Gap. Doubling Constant Parametrization of Weighted Problems: TSP, Max-Cut, and More","abstract":"Despite much research, hard weighted problems still resist super-polynomial improvements over their textbook solution. On the other hand, the unweighted versions of these problems have recently witnessed the sought-after speedups. Currently, the only way to repurpose the algorithm of the unweighted version for the weighted version is to employ a polynomial embedding of the input weights. This, however, introduces a pseudo-polynomial factor into the running time, which becomes impractical for arbitrarily weighted instances. In this paper, we introduce a new way to repurpose the algorithm of the unweighted problem. Specifically, we show that the time complexity of several well-known NP-hard problems operating over the $(\\min, +)$ and $(\\max, +)$ semirings, such as TSP, Weighted Max-Cut, and Edge-Weighted $k$-Clique, is proportional to that of their unweighted versions when the set of input weights has small doubling. We achieve this by a meta-algorithm that converts the input weights into polynomially bounded integers using the recent constructive Freiman's theorem by Randolph and Węgrzycki [ESA 2024] before applying the polynomial embedding.","short_abstract":"Despite much research, hard weighted problems still resist super-polynomial improvements over their textbook solution. On the other hand, the unweighted versions of these problems have recently witnessed the sought-after speedups. Currently, the only way to repurpose the algorithm of the unweighted version for the weig...","url_abs":"https://arxiv.org/abs/2601.00768","url_pdf":"https://arxiv.org/pdf/2601.00768v2","authors":"[\"Mihail Stoian\"]","published":"2026-01-02T17:59:15Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}