Papers for

optimization software developers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Stochastic algorithm improves convergence rates for convex problems

Improving the Last-Iterate Guarantees of Anytime Algorithms for Stochastic Monotone Variational Inequalities

Abstract: We analyze a stochastic algorithm with Halpern anchoring for constrained convex-concave problems and monotone variational inequalities. This algorithm is single-loop and single-call since it uses one unbiased sample of the gradient operator at every iteration to be applicable to monotone games with noisy feedback. With $t$ denoting the iteration counter, we prove the anytime last-iterate convergence rate of $O(t^{-1/4})$ for both gradient-mapping norm and restricted gap, improving the best-known rate $O(t^{-1/5})$ that was obtained for the restricted gap function. Our rates cover constrained problems with a potentially unbounded feasible set as well as a structured class of stochastic oracles without a bounded variance.

Mon 14 SeptMachine Learning
The gist
Solving complex mathematical problems that involve multiple players or variables often requires algorithms that can handle randomness and constraints efficiently. The authors studied a particular algorithm designed to work on these problems with uncertain or noisy feedback, improving how quickly it converges to a solution at each step. Their method uses fewer assumptions and simpler iterations while working on cases where the problem's scope might be very large or unbounded. This improvement means better performance and reliability when solving many practical problems modeled by these mathematical structures.
Open → 2609.15257v1

Pmms fairness does not always exist but guarantees hold for additive chores

Non-Existence of PMMS Allocations and a $4/3$-PMMS Guarantee for Additive Chores

Abstract: We study pairwise maximin share (PMMS) fairness for indivisible items with additive preferences. We give a polynomial-time reduction from chores to goods that preserves the existence of a PMMS allocation. Together with known nonexistence results for chores, this yields nonexistence for additive goods. In addition, we show that deciding if a given instance admits a PMMS allocation is NP-hard. We also give explicit instances whose PMMS factors are $226/227$ for goods and $1.102065$ for chores, certified by exact enumeration. Complementing these impossibility results, we prove that every additive-chore instance admits a $4/3$-PMMS allocation.

Wed 9 SeptComputer Science and Game Theory
The gist
Sometimes when dividing things that people dislike, called chores, it’s impossible to make everyone as fairly treated as a certain fairness measure called pairwise maximin share (PMMS) demands. The authors found a way to show that this difficulty also applies when dividing goods that people want. They proved that deciding if a perfectly fair PMMS allocation is possible is a hard problem to solve by a computer. Still, they showed that for chores, there is a way to make an allocation that is fairly close to the PMMS standard, within a factor of 4/3.
Open → 2609.10493v1

Standard bounds for mixed-integer bilevel programs cannot be consistently improved

On the Tightness of Standard Relaxations for Mixed-Integer Bilevel Linear Programs

Abstract: Exact algorithms for solving mixed-integer bilevel linear programs (MIBLPs) typically rely on sequences of lower and upper bounds that converge to the optimal value. These procedures are commonly initialized using the single-level relaxation (SLR), obtained by omitting the follower's optimality condition and solving the resulting single-level optimization problem. In this paper, we investigate whether, for broad classes of MIBLPs, the resulting standard bounds admit uniform improvements that can be computed within the same computational complexity regime. For pure continuous bilevel linear programs, we show that, unless $P = NP$, neither the SLR-based lower bound nor its associated upper bound can be uniformly improved in polynomial time, even for the class of min-max problems. We then extend this analysis to the class of pure integer min-max bilevel linear programs under the assumption that the polynomial hierarchy does not collapse. First, we show that the continuous relaxation of the SLR admits no uniform polynomial-time computable improvement. We then prove that neither the SLR itself nor its associated upper bound admits a uniform improvement by a polynomial-time algorithm with access to a mixed-integer linear programming (MILP) oracle. Importantly, this rules out uniform improvements by iterative MILP-based approaches, including cutting-plane-based and decomposition algorithms. Overall, our results demonstrate that the SLR-based bounds are, in a complexity-theoretic sense, unimprovable systematically within their natural computational regimes.

Wed 9 SeptComputational Complexity
The gist
Mixed-integer bilevel linear programs are complicated optimization problems involving two decision-makers, one acting first and the other reacting. People usually start solving these by relaxing the problem to a simpler one, ignoring the second decision-maker’s optimal choice. The authors show that for broad classes of these problems, this standard simpler version cannot be improved efficiently in a general way, unless major breakthroughs in computational theory occur. This means current methods for getting bounds in these problems are essentially as good as possible from a complexity perspective.
Open → 2609.10233v1