4 papers
The Online Steinitz Problem
Matteo Russo, Jiaye Wei
Inspired by Steinitz's celebrated result (1913) and recent online vector-balancing results of Kulkarni et al. (2024) and Aden-Ali (2026), we introduce the online Steinitz problem:…
On Feige's conjecture
Zipei Nie, Jiaye Wei
We present a short proof of Feige's conjecture: for independent nonnegative random variables with expectation one, the probability that their sum is less than is at least…
Polyhedral extended formulations that approximate the Gomory closure for packing problems
Friedrich Eisenbrand, Samuel Fiorini, Lars Rohwedder +1
We consider packing problems , with . A way to solve such problems is via tighteni…
Second Price Matching with Complete Allocation and Degree Constraints
Rom Pinchasi, Neta Singer, Lukas Vogl +1
We study the Second Price Matching problem, introduced by Azar, Birnbaum, Karlin, and Nguyen in 2009. In this problem, a bipartite graph (bidders and goods) is given, and the profi…