CS Paper Radar

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

Jannis Blauth, Rico Zenklusen

cs.DS ·submitted 2026-11-13 16:39 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

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.65
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

An 8/5 Rounding for Half-Integral Forest-BCR via Root Supports and Circuit Rank

cs.DS ·2026-08-22 ·Morteza Alimi
theory similarity 0.65
Abstract

We study the rounding of a supplied half-integral feasible solution of the root-assignment bidirected cut relaxation for Steiner Forest (Forest-BCR). Byrka, Grandoni, and Traub [IPCO 2025] proved a $16/9$ guarantee for a recursive framework that normalizes the LP point, selects a vertex set of maximum projected LP density, buys a minimum spanning tree on that set, contracts it, and recurses. We prove that the same framework has guarantee $8/5$. The new analysis keeps the orientation and the root label of each projected half-unit of LP mass. In a simple projection, the cut constraints at a terminal of degree two determine the root-assignment vector of every demand incident with it, and half-integrality leaves only two possibilities: a unit assignment to one root, which forces excess outdegree inside that root's support, or a split assignment to two roots, which forces overlap between their supports. For every connected component $C$ of the split-root graph this yields $ β_C\ \ge\ \frac{L_C}{2}$, where $β_C$ is the circuit rank of the union of the root supports in $C$ and $L_C$ is the number of its vertices of degree two in the full projection. Balancing the density certificate obtained from this inequality against the ordinary degree sum gives a vertex set of density at least $5/8$, and the inherited contraction lemma turns that into the $8/5$ rounding. For every $q\ge3$ we also construct a normalized half-integral point whose maximum projected density is exactly $5q/[2(4q-1)]$, so the universal projected-density bound is asymptotically tight.

0.22

Approximation algorithms via discrepancy with hard constraints

cs.DS ·2026-10-12 ·Mikhail Cherniavskii, Andrey Kupavskii, Stanislav Moiseev, Alexander Shekhovtsov
similarity 0.60
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.

0.29

Online and Incremental Fractional Vertex Cover on Trees

cs.DS ·2026-08-25 ·Júlia Baligács, Bartłomiej Bosek, Yann Disser, Andreas Emil Feldmann, Grzegorz Gutowski +3 more
publishedtheory similarity 0.59
Abstract

In this paper we study the fractional vertex cover problem on trees in two related models: online and incremental. In the online model, the vertices of the tree are known a priori and the edges arrive one at a time. The goal is to maintain a fractional vertex cover of the tree, i.e., an assignment of fractional weights from [0,1] to the vertices such that the weights of endpoints of every edge sum up to at least one. After each edge arrival, we need to modify the fractional vertex cover to cover the new edge as well. However, we can only increase the values assigned to vertices. The problem was studied before (in the vertex arrival model) by Wang and Wong, who motivated it as a generalization of the ski-rental problem, but also (more importantly) by its close connection to the dual online matching problem. They presented a 1.901-competitive algorithm for general graphs in the vertex arrival model. We present an $\frac{11}{6} \approx 1.83$-competitive algorithm for trees in the more general edge arrival model. In addition, we study the fractional vertex cover problem in an incremental model, where we again seek a fractional vertex cover after every update, but all the updates to the tree are known to the algorithm a priori. In this model, we give a 1.5-competitive algorithm and provide a matching lower bound.

0.46

Product-Aware Deterministic Rounding for Quantized Matrix Multiplication

cs.LG cs.DScs.IT ·2026-09-11 ·Piyush Sao, Narasinga Miniskar, Pedro Valero-Lara, Keita Teranishi, Sudip Seal
similarity 0.58
Abstract · 30 pages, 7 figures

Scalar rounding decisions interact through matrix multiplication. We study deterministic product-aware rounding after scales, clipping bounds, and grids are fixed, with each active scalar choosing between adjacent levels. For dynamic activation rounding, null-space reduction preserves the relaxed product while leaving at most $r$ fractional decisions, where $r$ is the rank of the active gap-weighted weight block. Conditional-expectation completion gives a deterministic polynomial-time algorithm with squared product error at most $ \mathrm{OPT}_{\mathrm{dyn}}+rν_{\max}^2/4$, where $\mathrm{OPT}_{\mathrm{dyn}}$ is the best admissible error and $ν_{\max}$ is the largest row norm of that block. For reusable static weights, the exact expected product-loss metric is the uncentered input second moment with fixed output bias; free bias recalibration yields the centered covariance. Exact optimization is NP-hard even at rank one. In balanced blocks with $K=1024$ and $r=16$, conditional- expectation completion attains a dither-normalized median error of $0.010$, compared with $0.899$ for round-to-nearest. Clipping-aware initialization reduces median normalized error by a factor of $43.4$ at ten-percent clipping. Held-out Digits experiments show that retaining the input mean or correcting the output bias improves median product error over round-to-nearest in all four tested bit-width and calibration-size settings.

0.30

Incremental Minimum Spanning Trees on a Napkin

cs.DS ·2026-11-03 ·Lucian Bicsi, Adrian Budău
similarity 0.58
Abstract · 20 pages, 5 figures, 3 tables

In the incremental minimum spanning forest problem, weighted edges arrive one at a time. After each insertion we must report the edge that leaves the minimum spanning forest, and queries ask for the bottleneck distance of two vertices: the smallest possible maximum edge cost on a path between them. Link-cut trees solve both in $O(\log n)$ amortized time. In 2021 we wrote the folklore BottleneckTree, a short competitive-programming structure that stores one parent pointer and one cost per vertex, and conjectured that it also runs in $O(\log n)$ amortized time. We show that this conjecture is false: on a family of inputs, its amortized cost per operation is $Ω(\sqrt{n})$. We then present a structure with the same state, two arrays and a single loop, and prove that it runs in $O(\log n)$ amortized time per insertion and per query. Unlike the AM-tree of Ding, Gu and Sun, which attains the same bound, it stores no subtree sizes and maintains no balance invariant. For a connected graph with distinct costs, the structure can be viewed as an implicit link-cut tree on the Kruskal reconstruction tree: each rotation corresponds to exactly one preferred-child change, and each skip acts on a stale path-parent pointer. In experiments it is 1.3-2.1 times faster than the folklore BottleneckTree on insertions, up to 480 times faster on its adversarial input, and 6.3-16 times faster than an explicit link-cut tree.

0.32

Two $(2+ε)$-Approximation Algorithms for Minimum Spanning Tree Interdiction

cs.DS ·2026-11-18 ·Junjie Luo, Changjun Wang, Chenhao Wang, Wei Yu
similarity 0.58
Abstract

Minimum spanning tree interdiction asks for edge deletions within a budget that maximize the weight of a remaining minimum spanning tree. We give two deterministic $(2+ε)$-approximation algorithms for every fixed $ε>0$, improving the previous best factor of $4$. Both algorithms respect the original budget and run in $N^{O(1/ε)}$ time for $0<ε\le1$, where $N$ is the binary input size. The first algorithm uses two weight thresholds to choose initial deletions that force every remaining spanning tree to contain edges at or above these thresholds. It then uses the remaining budget to further increase the MST weight through Lagrangian rounding. The second algorithm achieves the same guarantee through a different decomposition: it enumerates vertex partitions and heavy trees connecting their parts, then approximates a bounded-weight interdiction problem within the parts. An objective-preserving reduction from Maximum Components shows that, assuming the Small Set Expansion Hypothesis and $\mathsf P\ne\mathsf{NP}$, no deterministic polynomial-time $(2-δ)$-approximation exists for any fixed $0<δ<1$, even on simple graphs with weights in $\{0,1\}$. Thus, our approximation guarantee is conditionally tight up to an arbitrarily small additive constant. Finally, the MST guarantee yields a $(4+ε)$-approximation for metric-TSP interdiction.

0.15

Speedup-Aware Rounding for Scheduling Malleable Tasks with Precedence Constraints

cs.DS ·2026-11-11 ·Chi-Yeh Chen
similarity 0.58
Abstract · 31 pages; ancillary files contain the numerical verification programs

We study the scheduling of malleable tasks with precedence constraints on $m$ identical processors to minimize the makespan, assuming that the processing time of a task does not increase and its work does not decrease with the number of processors, and that the work is a convex function of the processing time. The standard two-phase method solves a linear program, rounds the fractional processing times to allotments, caps the allotments at a threshold $μ$, and runs list scheduling. We propose \emph{speedup-aware rounding}, which rounds a task to its slower allotment exactly when this allotment is at most a factor $a$ slower than the fractional processing time. We determine the worst-case increase of the work under this rule exactly and show that no per-task rounding rule with time factor $a$ does better. With $μ=\lceilβ(a)m\rceil$ the algorithm achieves the approximation ratio $13(30+\sqrt{493})/225\approx3.0162$ for every $m$, which improves the previous bound $2+\sqrt2\approx3.4142$; a single task with linear speedup shows that its ratio is at least $\approx2.9558$. For concave speedup functions, which include the roofline, communication, Amdahl and power-law models, the ratio becomes $\approx2.9739$, which improves the ratio $\approx3.2919$ of Jansen and Zhang. We also revisit the strictly decreasing case of our earlier work (Chen and Chu, 2013): the reported ratio $2.9549$ relies on an elimination step that is not valid. In this case the algorithm coincides with that of Jansen and Zhang up to its parameters, and with parameters chosen by the corrected analysis it guarantees their ratio $\approx3.2919$. Finally, without convexity no per-task rounding improves the known time--work trade-off, and the analysis cannot go below $(3+\sqrt5)/2$.

0.23