CS Paper Radar

Multiplicative Weights for Mixed Block Constraints and Maximum Multicommodity Flow

Vladimir Kolmogorov

cs.DS ·submitted 2026-11-01 14:00 UTC · v1

Abstract

We study multiplicative-weights (MWU) algorithms for block-separable feasibility problems containing both packing and covering constraints. Each iteration optimizes a weighted linear objective over one block, either chosen uniformly at random or visited in a fixed cyclic order. We show that the cyclic algorithm returns an $O(\varepsilon)$-approximate solution after $O(kρ\varepsilon^{-2}\log m)$ oracle calls where $k$ is the number of blocks and $ρ$ is the width of the oracle. The same holds for the randomized version with high probability. Previously, such bounds were shown when the coupling constraints have the same sign [Radzik'95; Villavicencio-Grigoriadis'96]. These analyses critically depended on monotonicity arguments that are not available in the mixed case. As an application, we obtain a deterministic $(1-\varepsilon)$-approximation for maximum multicommodity flow (M-MCF) using $O(k\varepsilon^{-2}\log m\log(km/\varepsilon))$ approximate single-commodity min-cost-flow calls. For planar graphs, and more generally for graph families admitting a near-linear-time min-cost-flow algorithm, this gives total running time $\widetilde O(km\varepsilon^{-2})$. Compared with the $O(km^{1+o(1)}\varepsilon^{-1})$ algorithm of [Chen-Graur-Sidford'25], this improves the dependence on $m$ for these graph families at the cost of a worse dependence on $\varepsilon$. Finally, we give an exponentiation-free finite-precision implementation of the cyclic algorithm. It represents each internal weight by a logarithmic-bit mantissa and exponent, while every price supplied to the block oracle is rational and has a polynomially bounded common denominator.

Comment
15 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Extending Tardos's Theorem to Separable Convex Quadratic Programming

cs.DS ·2026-10-05 ·Bin Cui, Hanqing Li, Xupeng Miao
theory similarity 0.63
Abstract · 13 pages, no figures. Substantially revised with a simplified algorithm and proofs. Title and author list updated

For an integer equality matrix $A\in\mathbb{Z}^{r\times m}$ of binary encoding length $\langle A\rangle$, Tardos's theorem solves linear programs using $\operatorname{poly}(r,m,\langle A\rangle)$ rational arithmetic operations and comparisons, independently of the right-hand side and objective coefficients. We extend this guarantee to continuous separable convex quadratic programming over $Ax=b$, $x\ge0$: the operation count is independent of the right-hand side, linear costs, and all nonnegative quadratic weights. The algorithm returns an exact optimal primal-dual pair or a certificate of infeasibility or unboundedness. All intermediate rational numbers have encoding lengths polynomial in the total input length. As an application, we obtain a strongly polynomial algorithm for continuous multicommodity flow with shared capacities and quadratic costs of aggregate arc flow, independently of demands, capacities, and cost coefficients. Objective compression and continuous-integer proximity yield a local solver returning a point close to an optimum. We relax nonnegativity on coordinates with zero optimal dual slack, minimize the largest remaining coordinate, and optimize over the relaxed coordinates. A descent LP over the recession cone provides a complementary bound. Circuit decomposition combines these bounds into a scale ensuring that each local call reveals a new coordinate. At most $m$ calls, followed by two LPs, recover an exact optimum and its dual certificate.

0.20

Path-constrained Packing on Trees

cs.DS ·2026-11-16 ·Samuel Fiorini, Raoul Luqué, Philipp Pabst, Britta Peis
similarity 0.61
Abstract · 36 pages, 5 figures, 1 table, 2 algorithms

An instance of Budgeted Path-constrained Packing on Trees (BPPT) consists of a graph $G$ together with a spanning tree $T$, a weight $w_e \in \mathbb{Z}_{\ge 0}$ for each tree edge $e \in E(T)$ and a budget $b_f \in \mathbb{Z}_{\ge 1}$ for each non-tree edge $f \in E(G) \setminus E(T)$. The goal is to find a maximum weight packing of fundamental cuts respecting the budgets. Equivalently, an instance of BPPT is an integer program of the form $\max \{w^\intercal x : Ax \le b,\ x \in \{0,1\}^n\}$ where $A \in \{0,1\}^{m \times n}$ is a transposed edge-path-tree matrix, $w \in \mathbb{Z}^n_{\ge 0}$ and $b \in \mathbb{Z}^m_{\ge 1}$. We define the congestion $C$ of a BPPT instance as the maximum number of non-zeros in a column of $A$. The unit congestion $UC$ is defined similarly, except that rows with $b_i \ge 2$ are ignored. We also consider the minimum budget $β:= \min \{b_i : i = 1, \ldots, m\}$. In this paper, we begin the study of BPPT through the lens of the three parameters $C$, $UC$ and $β$, and relative to the standard LP relaxation $\max \{w^\intercal x : Ax \le b,\ x \in [0,1]^n\}$. BPPT generalizes the independent set problem in graphs of maximum degree at most $C$ and is a special case of the $b$-matching problem in hypergraphs of rank at most $C$. We obtain approximation algorithms for BPPT with factors $2+UC/2$, $1+C/2$ and $β/(β-1)$ for $β\geq 2$. These bounds are relative to the standard LP relaxation and, as we show, integrality gap tight with respect to parameters $UC$ and $β$, and almost integrality gap tight relative to $C$. We complement these results with a $\lceil (C+1)/3 \rceil$-approximation for fixed $C$ which is not relative to the standard LP relaxation and has $\textsf{XP}$ running time parameterized by $C$.

0.24

A Deterministic $0.401$-Approximation for Non-monotone Submodular Maximization under Matroid Constraints

cs.DS math.OC ·2026-10-12 ·Shengminjie Chen, Kaifeng Lin, Xiaoming Sun, Jialin Zhang
similarity 0.60
Abstract

Submodular maximization arises in a wide range of combinatorial optimization problems and has been extensively studied from the perspective of approximation algorithms. For maximizing nonnegative, non-monotone submodular functions subject to a matroid constraint, randomized algorithms achieve a $0.401$-approximation, whereas obtaining comparable deterministic guarantees remains challenging. In this paper, we present a deterministic $0.401$-approximation algorithm in the exact value and independence oracle model, improving upon the previous deterministic guarantee of $(0.385-\varepsilon)$ \cite{ChenGLSZ2026}. Our algorithm builds on the extended multilinear extension and provides a deterministic implementation of the recursive guided framework underlying the randomized $0.401$-approximation algorithm. The main technical ingredient is a direction oracle supported on at most two partitioned matroid bases. This oracle simultaneously satisfies the growth condition required by the extended-multilinear update and an approximate stationarity condition needed to construct the recursive guides. The resulting finite-support representation enables exact evaluation of the relevant expectations and marginal values without random sampling. The algorithm uses polynomially many value- and independence-oracle queries.

0.14

Breaking the 1/3 Barrier for constrained $\boldsymbol{k}$-Submodular Maximization: A Proportional Top-2 Randomized Framework

cs.DS ·2026-09-14 ·Siyuan Chen, Shengminjie Chen, Suixiang Gao, Zheyu Jiang, Chenhao Wang +1 more
similarity 0.59
Abstract

$k$-submodularity generalizes submodularity by allowing each selected element to be assigned one of $k$ labels. We study the maximization of a non-monotone $k$-submodular function, where $k\ge2$, under matroid and knapsack constraints. We develop a proportional top-2 randomized framework that achieves an approximation ratio of $\sqrt2-1\approx0.4142$ under either constraint, breaking the previous $1/3$ barrier. Once an element is selected, its label is chosen from the two labels with the largest marginal gains, with probabilities proportional to their positive parts. The analysis separates replacement, pure-addition, and residual-deletion losses, and proves a sharp local loss certificate for this rule. We then give a Bellman analysis using the same local certificate. It gives a $1/2$-approximation under a cardinality constraint and strengthens the knapsack guarantee to $1/2$ without changing the algorithm. The $1/2$ guarantees are oracle-optimal for $k=2$ and asymptotically tight as $k\to\infty$. The value-oracle complexities are $O(Bnk)$ for cardinality, where $B$ is the cardinality bound, $O(n^2k)$ for matroid, and $O(n^3k^2)$ for knapsack.

0.20

Approximating the Chvátal--Gomory Closure of Capacity-Bounded Min-Closed Systems

cs.DS ·2026-09-28 ·Stefano Huber, Monaldo Mastrolilli
publishedtheory similarity 0.59
Abstract · 19 pages, a short version of this paper appears in the proceedings of ISAAC 2026

Optimizing over the {0, 1/2} rank-1 Chvàtal-Gomory (CG) closure of a binary integer linear program is NP-hard. While polynomial-time approximation schemes (PTAS) are established for monotone packing and covering formulations, extending these guarantees to mixed-sign variants remains an open challenge. In this paper, we study the approximability of the CG closure for k-slack bounded (capacity-bounded) min-closed systems, a generalized packing formulation with mixed-sign constraints that extends weighted Boolean Horn logic. In these systems, a constant upper bound $k \ge 1$ bounds the ratio between the negative penalty coefficient $q$ and the right-hand side capacity $b$ of every constraint, enforcing $q \le k \cdot b$. We prove that a constant-degree sum-of-squares relaxation yields a PTAS for maximizing linear objectives over the first CG closure generated by multipliers in $\{0\}\cup[\tfrac1f,1]$, for any constant integer $f \ge 2$. This closure is contained in the {0, 1/2} rank-1 CG closure.Optimizing over the {0, 1/2} rank-1 CG closure of a binary integer linear program is NP-hard. While PTASes are established for monotone packing and covering formulations, extending these guarantees to mixed-sign variants remains an open challenge. In this paper, we study the approximability of the CG closure for \emph{$k$-slack bounded (capacity-bounded) min-closed systems}, a generalized packing formulation with mixed-sign constraints that extends weighted Boolean Horn logic. In these systems, a constant upper bound $k \ge 1$ bounds the ratio between the negative penalty coefficient $q$ and the right-hand side capacity $b$ of every constraint, enforcing $q \le k \cdot b$. We prove that a constant-degree sum-of-squares relaxation yields a PTAS for maximizing linear objectives over the first CG closure generated by multipliers in $\{0\}\cup[\tfrac1f,1]$, for any constant integer $f \ge 2$.

0.61

Nearly-Linear Query Algorithm for Submodular Maximization subject to a Matroid Constraint

cs.DS ·2026-11-03 ·Tatsuya Terao
similarity 0.59
Abstract · 21 pages

We consider monotone submodular maximization subject to a matroid constraint. The seminal continuous greedy algorithm of Calinescu, Chekuri, Pál, and Vondrák~[SICOMP'11] achieves the tight approximation of $(1-1/e)$. Since then, a line of works by Badanidiyuru and Vondrák~[SODA'14], Buchbinder, Feldman, and Schwartz~[SODA'15 \& MOR'17], Kobayashi and Terao~[ICALP'24], Buchbinder and Feldman~[FOCS'24 \& SICOMP'25], and Buchbinder and Feldman~[STOC'25] has developed efficient $(1-1/e-\varepsilon)$-approximation algorithms for this problem. We present a combinatorial randomized $(1-1/e-\varepsilon)$-approximation algorithm that requires $\tilde{O}_{\varepsilon}(n)$ independence-oracle and value-oracle queries, where $n$ is the number of elements in the matroid. This is the first $(1-1/e-\varepsilon)$-approximation algorithm with both independence-oracle and value-oracle query complexities nearly-linear in $n$ and polynomial in $1/\varepsilon$. To achieve this, we develop a new local search algorithm, which we call \emph{protected local search}, based on the potential function of Buchbinder and Feldman~[FOCS'24 \& SICOMP'25].

0.18

Consistent Submodular Maximization with Full Foresight

cs.DS cs.LG ·2026-11-04 ·Eric Balkanski, Paul Dütting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard +2 more
theory similarity 0.59
Abstract

Online algorithms with bounded recourse face three intertwined obstacles: uncertainty about the future, computational limits, and a limited budget for changes. We ask a fundamental question that separates consistency from the other two: what does solution stability cost when the entire future is known and computation is unlimited? We answer this question for monotone submodular maximization, where an algorithm must maintain a solution of at most $k$ arrived elements, with a constant number of changes per step. We determine the optimal approximation thresholds: $3/4$ for deterministic algorithms and $ξ^\star \approx 0.7942$ for randomized algorithms. For every $\varepsilon>0$, we get within $\varepsilon$ of these thresholds with worst-case recourse polynomial in $1/\varepsilon$, independent of $k$ and the stream length. We prove matching impossibility results even for coverage functions. We attain the sharp bounds by optimally balancing two opposing forces: preparing for future arrivals and protecting the current solution. For randomized algorithms, we use addition robustness against prefixes of the known future, which we analyze tightly via an interval-selection problem. For deterministic algorithms, we introduce certificates, paths in a fractional relaxation that maintain high value, which we round into an update schedule.

0.44

Tight Approximation Results for Matroid Optimization with a Linear Constraint

cs.DS ·2026-09-23 ·Ilan Doron-Arad, Hadas Shachnai, Gilad Shmerler
similarity 0.58
Abstract

We study the following class of matroid optimization problems with a linear constraint (P-MOL). Given a matroid M=(E,I), two weight functions $v,w:E\to R_{\ge 0}$, and a threshold $L\in R_{\ge 0}$, find $opt v(S)$ where S is either an independent set or a base of M satisfying a budget-type constraint: $w(S)\le L$ or $w(S)\ge L$, and $opt\in\{min,max\}$. P-MOL provides a unified representation for a broad family of NP-hard optimization problems, including budgeted matroid independent set, constrained minimum-basis, and knapsack-cover variants with a matroid constraint. Also, it naturally extends to multiple matroid constraints. In particular, we consider the matroid intersection cover (MIC) problem, where feasibility is defined by the common independent sets of two matroids and one seeks minimum $v(S)$ subject to $w(S)\ge L$. Our main result is a unified EPTAS for all nontrivial P-MOL variants, obtained by generalizing a technique of Hassin and Levin (SIAM J. Comput., 2004) for solving the constrained minimum spanning tree problem. Specifically, for any fixed $ε>0$, we present an algorithm running in time $|E|^{O(1)} (1/{ε^2})^{O(1/ε)}$ that outputs a feasible solution S whose value is at most $(1+ε)OPT$ for minimization variants and at least $(1-ε)OPT$ for maximization variants. This resolves the complexity status of all members of P-MOL, as none of these problems admits an FPTAS (Doron-Arad, Kulik and Shachnai, ICALP'24). Finally, we separate the P-MOL family from its extension to matroid intersection. We show that an EPTAS is unlikely to exist for the matroid intersection variant of P-MOL under a covering constraint, whereas an EPTAS is known to exist under a budget constraint. This highlights a qualitative difference between these two types of linear constraints that does not arise in the single-matroid setting.

0.14