181 citations · 620 across the 171 of their papers we have counts for
7 papers · 1 filter
Strong reductions for extended formulations
Gábor Braun, Sebastian Pokutta, Aurko Roy
We generalize the reduction mechanism for linear programming problems and semidefinite programming problems from [arXiv:1410.8816] in two ways 1) relaxing the requirement of affine…
Solving MIPs via Scaling-based Augmentation
Pierre Le Bodic, Jeffrey W. Pavelka, Marc E. Pfetsch +1
Augmentation methods for mixed-integer (linear) programs are a class of primal solution approaches in which a current iterate is augmented to a better solution or proved optimal. I…
Sequential Information Guided Sensing
Ruiyang Song, Yao Xie, Sebastian Pokutta
We study the value of information in sequential compressed sensing by characterizing the performance of sequential information guided sensing in practical scenarios when informatio…
An information diffusion Fano inequality
Gábor Braun, Sebastian Pokutta
In this note, we present an information diffusion inequality derived from an elementary argument, which gives rise to a very general Fano-type inequality. The latter unifies and ge…
The matching problem has no small symmetric SDP
Gábor Braun, Jonah Brown-Cohen, Arefin Huq +5
Yannakakis showed that the matching problem does not have a small symmetric linear program. Rothvoß recently proved that any, not necessarily symmetric, linear program also has exp…
No Small Linear Program Approximates Vertex Cover within a Factor
Abbas Bazzi, Samuel Fiorini, Sebastian Pokutta +1
The vertex cover problem is one of the most important and intensively studied combinatorial optimization problems. Khot and Regev (2003) proved that the problem is NP-hard to appro…
Sequential Sensing with Model Mismatch
Ruiyang Song, Yao Xie, Sebastian Pokutta
We characterize the performance of sequential information guided sensing, Info-Greedy Sensing, when there is a mismatch between the true signal model and the assumed model, which m…