CS Paper Radar

Approximation algorithms via discrepancy with hard constraints

Mikhail Cherniavskii, Andrey Kupavskii, Stanislav Moiseev, Alexander Shekhovtsov

cs.DS ·submitted 2026-10-12 02:35 UTC · v1

Abstract

In this paper, we present a discrepancy-based approach to cost-preserving rounding under hard constraints. Starting from a feasible fractional solution, our rounding procedure preserves the designated hard constraints, never increases the linear objective, and bounds the error in the remaining constraints by the discrepancy of a suitable column-difference matrix. Our second discrepancy-theoretic result bounds the discrepancy of a matrix in terms of a novel column parameter, called mountain distance. This notion captures ordered structural features of a matrix which are invisible to the classical Beck--Fiala and Komlós column-norm parameters. We show a variety of applications of these two results. In particular, we obtain new results for min-cost unsplittable flows, bounded-turn routing in grids and tori, rainbow prefix hypergraph decomposition, and $2$-multicast scheduling.

Closest papers

Nearest neighbours by meaning across the whole index.

Roundtrip All-Pairs Shortest Paths in Directed Graphs

cs.DS ·2026-11-03 ·Shiri Chechik, Gur Lifshitz
similarity 0.64
Abstract

We study approximation algorithms for All-Pairs Shortest Paths (APSP) in directed graphs under the roundtrip metric. In directed graphs, even finite-factor approximation of ordinary one-way distances must distinguish reachable from unreachable vertex pairs, and therefore computes transitive closure, a problem equivalent to Boolean matrix multiplication (BMM) under standard reductions. The roundtrip distance, defined as $\text{dist}_G(u \leftrightarrows v) = \text{dist}_G(u \to v) + \text{dist}_G(v \to u)$, offers a natural and robust relaxation. It measures the cost of traveling from $u$ to $v$ and back, satisfies the triangle inequality, and is inherently symmetric. While this metric has become central to the study of directed roundtrip spanners and compact routing, the fundamental problem of all-pairs roundtrip distance approximation has remained largely unexplored. In this work, we present a comprehensive study of roundtrip APSP and distance oracles, presenting several new lower and upper bounds. On the algorithmic side, our main result is a combinatorial algorithm that computes a stretch-$3$ approximation to all-pairs roundtrip distances in $\widetilde{O}(n^2 + \min\{m\sqrt{n},\, m^{1/3}n^{5/3}\})$ time. For edge weights in $[1,W]$, we also obtain a $(3+\varepsilon)$-approximation in $\widetilde O((n^{2.037}+nm^{2/3})\log(nW)/\varepsilon)$ time and a $(4+\varepsilon)$-approximation in $\widetilde O(n^{2.032}\log(nW)/\varepsilon)$ time using fast matrix multiplication. On the hardness side, we show that any stretch below $3$ would imply a breakthrough for BMM. We also obtain additional tradeoffs between stretch and running time.

0.27

A Framework for Cost-Preserving Rounding with Applications to Laminar Thin Trees

cs.DS ·2026-11-13 ·Jannis Blauth, Rico Zenklusen
similarity 0.60
Abstract

In the context of finding thin trees, like laminarly-thin trees or globally-thin trees, it turned out to be challenging to round a fractional solution to an integral one without losing cost, while only having a constant-factor violation of the thinness constraints. We provide a general framework for this problem, in a much broader context, that reduces the problem to finding a certain type of rounding algorithm with only an approximate prize guarantee. We show that, up to a change in constants, the rounding problem with approximate prize guarantee that we use is equivalent to the original question. As an application, we obtain a polynomial-time algorithm that finds a laminar constantly-thin tree of cost no higher than the one of the natural linear programming solution, thus obtaining the first result without cost loss of this type (even for the special case of chain-constrained trees). Moreover, our framework gives a new perspective on how to approach the problem of finding globally-thin trees without cost loss.

0.32

Vector Balancing in Polynomial Time

cs.DS math.CO ·2026-09-20 ·Shengtao Guo, Ethan X. Fang, Junwei Lu
hot directionhighly cited similarity 0.59
Abstract · 23 pages, no figures

The Komlós problem asks for signs $\varepsilon\in\{-1,1\}^n$ with $\|A\varepsilon\|_\infty$ bounded by an absolute constant whenever the columns of $A\in\mathbb R^{m\times n}$ have Euclidean norm at most $1$. We give the first polynomial-time algorithm for this problem in the unit-cost real-RAM model. Our deterministic algorithm achieves discrepancy at most $8272$. As a consequence, we obtain a deterministic $O(\sqrt t)$-discrepancy algorithm for the Beck-Fiala problem on set systems in which each element belongs to at most $t$ sets. Our algorithm rounds a fractional coloring while keeping the row sums bounded. Its key idea is to keep the number of nearly tight row constraints small relative to the number of active coordinates. We achieve this through a spectral bound based on a weighted Gram matrix of squared row entries. We maintain the bound using a cubic spectral potential and negative-curvature updates that satisfy the required linear constraints.

0.58

A PTAS for Euclidean Capacitated Vehicle Routing

cs.DS ·2026-11-13 ·Zachary Friggstad, Fabrizio Grandoni, Ramin Mousavi, Kinter Ren, Mohammad R. Salavatipour
top venuehot direction similarity 0.59
Abstract

In the Capacitated Vehicle Routing Problem (CVRP), introduced by Dantzig and Ramser in 1959, we are given an $n$-node graph $G=(V,E)$ with metric edges costs $c(e)$, a depot $r\in V$, and an integer vehicle capacity $Q$. The goal is to find a minimum-cost collection of tours, each containing the depot and visiting at most other $Q$ nodes, such that the tours cover all the nodes. In this paper we focus on the Euclidean CVRP problem, where the nodes represent points on $\mathbb{R}^2$, and the edge costs are the respective Euclidean distances. Euclidean CVRP generalizes the classical NP-hard Euclidean TSP problem (the special case with $Q=n-1$), that admits a PTAS [Arora FOCS'96/Mitchell SODA'96]. A long-standing open problem has been generalizing the latter PTAS to Euclidean CVRP. A polynomial-time $(2+ε)$-approximation for this problem follows from the PTAS for Euclidean TSP and the tour-partitioning technique for CVRP [Haimovich, Kan Math. OR'85]. This was the best known until a recent improvement of the approximation factor to slightly below 2 [Friggstad, Grandoni, Mousavi SODA'26]. There have been a series of papers presenting improved QPTASs by Das and Mathieu [SODA'10] (time $n^{\log^{O(1/ε)}n}$), Jayaprakash and Salavatipour [SODA'22] (time $n^{O_ε(\log^6 n)}$), and recently Sitters [ArXiV'25] (time $n^{O_ε(\log\log n)}$). In this paper, we solve the mentioned long-standing open problem by presenting a PTAS for Euclidean CVRP.

0.46

Simpler Algorithms for Capacitated $k$-Median with $(1 + ε)$-Violations Using New Inequalities

cs.DS ·2026-10-16 ·Han Dai, Shi Li
published similarity 0.58
Abstract · Accepted at SOSA 2027

We revisit the capacitated $k$-median problem, focusing on constant-factor approximation algorithms with either $(1+ε)$-cardinality or capacity violations. Previous results [DemirciL16, Li16} achieve an $O_ε(1)$-approximation with $(1+ε)$-violations via complex extended configuration linear programming formulations with the round-or-cut framework. We propose a simpler, unified round-or-cut framework that handles both cardinality and capacity violation settings. Our main technical contribution is a mechanism that directly utilizes the costs of local instances to generate valid inequalities. Specifically, we partition the metric space into local pieces of size $O(1/ε)$ as in previous work, and construct instances of capacitated clustering with penalties, which allow client demands to be unserved at a penalty cost. Solving these local instances yields lower bounds on the original LP cost, yielding valid LP constraints. In contrast, previous approaches rely on complex extended configuration LPs over connection variables $x_{ij}$'s and opening variables $y_i$'s. As a secondary contribution, our approach achieves an improved running time of $\text{poly}(n, 1/ε)$, bypassing the exponential dependence on $1/ε$ required to solve the previous extended configuration LPs. Instead of solving the local instances optimally in time exponential in $1/ε$, we obtain $O(1/ε)$-approximate solutions in $\text{poly}(n, 1/ε)$ time. Finally, for the cardinality-violation setting, our algorithm opens a set of at most $(1+ε)k$ $\textit{distinct}$ facilities, and thus gives a bicriteria approximation in the $\textit{hard-capacitated}$ setting. In contrast, the algorithm of [Li16] may open the same facility multiple times.

0.33

Standard Quadratic Formulations of Many NP Problems: A Simplex-Based Compilation Framework for Combinatorial Optimization

cs.ET ·2026-10-01 ·Mohammad-Ali Miri, Babak Emami, PoJen Wang
similarity 0.58
Abstract

The standard quadratic program (StQP) minimizes a quadratic form over nonnegative variables that sum to one. We compose classical graph reductions with regularized Motzkin--Straus clique formulations to express discrete optimization problems in this continuous domain. The graph matrix has diagonal entries $τ$, zeros on edges, and ones on nonedges. For $0<τ<1$, its minimum is $τ/ω(G)$, where $ω(G)$ is the clique number. Its strict local minimizers are precisely the uniform distributions on maximal cliques, and its global minimizers encode maximum cliques. At $τ=1/2$, integer scaling gives coefficients in $\{0,1,2\}$ and minimum $1/ω(G)$, yielding an NP-complete StQP threshold problem with a restricted coefficient alphabet. We give explicit formulations for satisfiability, coloring, Hamiltonian cycles, independent set, vertex cover, set packing, three-dimensional matching, and graph isomorphism. A regularized weighted clique formulation combined with local-state compatibility graphs gives an exact compiler for finite-domain factor models specified by complete local tables, including QUBO, with at most four simplex coordinates per binary pair factor. The catalog covers Karp's 21 problems: twelve use direct graph formulations, and nine use factor-state formulations, including six obtained through binary-linear feasibility. For each route we record dimensions, coefficient structure, and recovery rules. We analyze interaction count, coefficient range, objective separation, perturbation tolerance, support recovery, and decoding overhead. The separation bounds quantify the effects of clique size, factor weights, and offsets. In the complete factor-state construction, every assignment, including each suboptimal assignment, is a strict local minimum.

0.16

Paying for Fractional Error: Tight Constant-Round Approximation of Covering Problems with Short Broadcasts

cs.DS cs.DC ·2026-11-01 ·Saeed Amiri, Sebastian Siebertz, Wojciech Wawrzyniak
theory similarity 0.58
Abstract

We present a general framework for deterministic constant-round approximation of covering problems in sparse networks in the broadcast CONGEST model, where every vertex broadcasts the same $O(\log n)$-bit message to all its neighbors. The framework combines two independent tools. The first is a solver that computes a $(1+δ)$-approximate solution of any local covering linear program with bounded positive integer costs on every class that excludes a fixed minor. The second is a rounding principle: a rounding rule that saves a fixed fraction of its own output, for every feasible input, pays for a solver error fixed in advance, so that an approximate fractional solution yields an exact coefficient. For ordinary domination, we achieve a $2a+1$ approximation against the fractional optimum $γ_f(G)$ for every fixed rational $a\ge1$, whenever every minor has a ratio of edges to vertices of at most $a$. On planar graphs this is seven, matching the lower bound of Hilke, Lenzen, and Suomela. The coefficients are also optimal at bounded treewidth and pathwidth, for $K_t$-minor-free graphs with $3\le t\le9$, on triangle-free planar graphs (five), and on planar graphs of large girth, where it approaches the optimal three. On every fixed surface the exact bound is $7γ(G)$, and we show that a bound of $7γ_f(G)$ is impossible on some fixed surfaces even sequentially. For total domination, on graphs without isolated vertices and under the same minor-density assumption, the exact coefficient is $2a$ against the fractional optimum, including the optimal six on planar graphs. Red-blue domination, and hence set cover and hitting set on planar incidence graphs, has the optimal limiting coefficient four. Our method also gives randomized constant-round and deterministic $O(\log^* n)$-round $(1+\varepsilon)$-approximation schemes, with the randomized cost guarantee holding in expectation.

0.45

A polynomial-time approximation scheme for the weighted Euclidean Minimum Latency Problem in fixed dimension

cs.DS math.CO ·2026-11-11 ·Daniel Skachkov, Yuriy Dorn
similarity 0.57
Abstract

In the Traveling Salesman Problem, a route must visit all customers and return to its starting point while minimizing its total length. The Minimum Latency Problem, also known as the Traveling Repairman Problem, instead minimizes the sum of the times at which customers are first visited. We give a deterministic polynomial-time approximation scheme for the weighted Euclidean Minimum Latency Problem in every fixed dimension, with arbitrary nonnegative customer weights. Our proof restricts the form of a solution in three steps, each with a controlled increase in cost. First, a decomposition based on Sitters' method assigns customers to phases that start and end at the root. Second, within each phase, we divide the route into a constant number of blocks and charge each customer at the end of its assigned block. The resulting objective is a nonnegative linear combination of block lengths. Third, we add an auxiliary dimension and use a fixed Minkowski norm to close each block path into a tour. Arora's closed-tour estimate then gives paths that cross the boundaries of a common dissection only at designated portals and a bounded number of times per face. A dynamic program optimizes the restricted objective, and projecting its paths back to the original space gives the final route. Rounding weights and coordinates keeps the state space polynomial.

0.30