Mind the Gap. Doubling Constant Parametrization of Weighted Problems: TSP, Max-Cut, and More
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914325350842368 |
|---|---|
| author | Stoian, Mihail |
| author_facet | Stoian, Mihail |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_00768 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Mind the Gap. Doubling Constant Parametrization of Weighted Problems: TSP, Max-Cut, and More Stoian, Mihail Data Structures and Algorithms 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. |
| title | Mind the Gap. Doubling Constant Parametrization of Weighted Problems: TSP, Max-Cut, and More |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2601.00768 |