Copertina

Mind the Gap. Doubling Constant Parametrization of Weighted Problems: TSP, Max-Cut, and More

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autore principale:	Stoian, Mihail
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

TSP Escapes the $O(2^n n^2)$ Curse
di: Stoian, Mihail
Pubblicazione: (2024)

Did Fourier Really Meet Möbius? Fast Subset Convolution via FFT
di: Stoian, Mihail
Pubblicazione: (2024)

Approximate Min-Sum Subset Convolution
di: Stoian, Mihail
Pubblicazione: (2024)

The Art of Staying Ahead of Deadlines: Improved Algorithms for the Minimum Tardy Processing Time
di: Stoian, Mihail
Pubblicazione: (2024)

Improved Approximation Algorithms for (1,2)-TSP and Max-TSP Using Path Covers in the Semi-Streaming Model
di: Alipour, Sharareh, et al.
Pubblicazione: (2025)

Approximation Schemes for Orienteering and Deadline TSP in Doubling Metrics
di: Ren, Kinter, et al.
Pubblicazione: (2024)

A Lower Bound for the Max Entropy Algorithm for TSP
di: Jin, Billy, et al.
Pubblicazione: (2023)

Approximating Asymmetric A Priori TSP beyond the Adaptivity Gap
di: Christalla, Manuel, et al.
Pubblicazione: (2025)

On the Optimal Linear Contraction Order of Tree Tensor Networks, and Beyond
di: Stoian, Mihail, et al.
Pubblicazione: (2022)

Local Max-Cut on Sparse Graphs
di: Schwartzman, Gregory
Pubblicazione: (2023)

Max-Cut with Multiple Cardinality Constraints
di: Makarychev, Yury, et al.
Pubblicazione: (2025)

Streaming Max-Cut in General Metrics
di: Jiang, Shaofeng H. -C., et al.
Pubblicazione: (2025)

A Linear Time Gap-ETH-Tight Approximation Scheme for Euclidean TSP
di: Mömke, Tobias, et al.
Pubblicazione: (2024)

Max Cut with Small-Dimensional SDP Solutions
di: Chang, Hsien-Chih, et al.
Pubblicazione: (2026)

Streaming and Massively Parallel Algorithms for Euclidean Max-Cut
di: Menand, Nicolas, et al.
Pubblicazione: (2025)

Online Metric TSP
di: Bertram, Christian
Pubblicazione: (2025)

Faster All-Pairs Minimum Cut: Bypassing Exact Max-Flow
di: Kenneth-Mordoch, Yotam, et al.
Pubblicazione: (2025)

Deterministic Edge Connectivity and Max Flow using Subquadratic Cut Queries
di: Anand, Aditya, et al.
Pubblicazione: (2024)

On Approximation of Robust Max-Cut and Related Problems using Randomized Rounding Algorithms
di: Shi, Haoyan, et al.
Pubblicazione: (2024)

On the Approximability of Max-Cut on 3-Colorable Graphs and Graphs with Large Independent Sets
di: Ghoshal, Suprovat, et al.
Pubblicazione: (2026)

Dual Charging for Half-Integral TSP
di: Klein, Nathan, et al.
Pubblicazione: (2025)

Approximating Prize-Collecting Variants of TSP
di: Alimi, Morteza, et al.
Pubblicazione: (2024)

4/3-Approximation of Graphic TSP
di: Çivril, Ali
Pubblicazione: (2023)

A Survey of Approximability Results for Traveling Salesman Problems using the TSP-T3CO Definition Scheme
di: Saller, Sophia, et al.
Pubblicazione: (2023)

A Simpler Approach for Monotone Parametric Minimum Cut: Finding the Breakpoints in Order
di: Beines, Arne, et al.
Pubblicazione: (2024)

Improved FPT Approximation for Non-metric TSP
di: Bampis, Evripidis, et al.
Pubblicazione: (2024)

Sublinear Algorithms for TSP via Path Covers
di: Behnezhad, Soheil, et al.
Pubblicazione: (2023)

Robust Multiagent Collaboration Through Weighted Max-Min T-Joins
di: Alipour, Sharareh
Pubblicazione: (2026)

Deterministic Near-Linear Time Minimum Cut in Weighted Graphs
di: Henzinger, Monika, et al.
Pubblicazione: (2024)

Parameterized Approximation Algorithms for TSP on Non-Metric Graphs
di: Zhao, Jingyang, et al.
Pubblicazione: (2025)

Matroid-Based TSP Rounding for Half-Integral Solutions
di: Gupta, Anupam, et al.
Pubblicazione: (2021)

Waiting is not easy but worth it: the online TSP on the line revisited
di: Chen, Pei-Chuan, et al.
Pubblicazione: (2019)

A Polylogarithmic Competitive Algorithm for Stochastic Online Sorting and TSP
di: Kalavas, Andreas, et al.
Pubblicazione: (2025)

A Polylogarithmic Competitive Algorithm for Stochastic Online Sorting and TSP
di: Kalavas, Andreas, et al.
Pubblicazione: (2025)

No Quantum Advantage in Decoded Quantum Interferometry for MaxCut
di: Parekh, Ojas
Pubblicazione: (2025)

Improved Upper Bounds for the Directed Flow-Cut Gap
di: Bodwin, Greg, et al.
Pubblicazione: (2026)

The Min Max Average Cycle Weight Problem
di: Elmalem, Noga Klein, et al.
Pubblicazione: (2025)

Breaking the O(mn)-Time Barrier for Vertex-Weighted Global Minimum Cut
di: Chuzhoy, Julia, et al.
Pubblicazione: (2025)

Better approximation guarantee for Asymmetric TSP
di: Vygen, Jens
Pubblicazione: (2026)

Optimal Approximations for the Requirement Cut Problem on Sparse Graph Classes
di: Mallek, Nadym, et al.
Pubblicazione: (2025)