research
∙
05/18/2023
Mode Connectivity in Auction Design
Optimal auction design is a fundamental problem in algorithmic game theo...
share
research
∙
11/07/2022
Approximating Nash Social Welfare by Matching and Local Search
For any ε>0, we give a simple, deterministic (6+ε)-approximation algorit...
research
∙
09/20/2022
On the Correlation Gap of Matroids
A set function can be extended to the unit cube in various ways; the cor...
research
∙
06/17/2022
Interior point methods are not worse than Simplex
Whereas interior point methods provide polynomial-time linear programmin...
research
∙
11/15/2021
On Circuit Diameter Bounds via Circuit Imbalances
We study the circuit diameter of polyhedra, introduced by Borgwardt, Fin...
research
∙
08/08/2021
Circuit imbalance measures and linear programming
We study properties and applications of various circuit imbalance measur...
research
∙
07/14/2021
On complete classes of valuated matroids
We characterize a rich class of valuated matroids, called R-minor valuat...
research
∙
07/12/2021
Approximating Equilibrium under Constrained Piecewise Linear Concave Utilities with Applications to Matching Markets
We study the equilibrium computation problem in the Fisher market model ...
research
∙
09/30/2020
Approximating Nash Social Welfare under Rado Valuations
We consider the problem of approximating maximum Nash social welfare (NS...
research
∙
09/10/2020
Revisiting Tardos's Framework for Linear Programming: Faster Exact Solutions using Approximate Solvers
In breakthrough work, Tardos (Oper. Res. '86) gave a proximity based fra...
research
∙
07/15/2020
Directed Shortest Paths via Approximate Cost Balancing
We present an O(nm) algorithm for all-pairs shortest paths computations ...
research
∙
04/18/2020
A Strongly Polynomial Label-Correcting Algorithm for Linear Systems with Two Variables per Inequality
We present a strongly polynomial label-correcting algorithm for solving ...
research
∙
12/12/2019
A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix
Following the breakthrough work of Tardos in the bit-complexity model, V...
research
∙
09/17/2018