181 citations · 620 across the 171 of their papers we have counts for
5 papers · 1 filter
Affine reductions for LPs and SDPs
Gábor Braun, Sebastian Pokutta, Daniel Zink
We define a reduction mechanism for LP and SDP formulations that degrades approximation factors in a controlled fashion. Our reduction mechanism is a minor restriction of classical…
Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization via Information Theory
Gábor Braun, Cristóbal Guzmán, Sebastian Pokutta
We present an information-theoretic approach to lower bound the oracle complexity of nonsmooth black box convex optimization, unifying previous lower bounding techniques by identif…
Info-Greedy sequential adaptive compressed sensing
Gabor Braun, Sebastian Pokutta, Yao Xie
We present an information-theoretic framework for sequential adaptive compressed sensing, Info-Greedy Sensing, where measurements are chosen to maximize the extracted information c…
Pricing and clearing combinatorial markets with singleton and swap orders: Efficient algorithms for the futures opening auction problem
Johannes C. Müller, Sebastian Pokutta, Alexander Martin +3
In this article we consider combinatorial markets with valuations only for singletons and pairs of buy/sell-orders for swapping two items in equal quantity. We provide an algorithm…
The matching polytope does not admit fully-polynomial size relaxation schemes
Gábor Braun, Sebastian Pokutta
The groundbreaking work of Rothvoß [arxiv:1311.2369] established that every linear program expressing the matching polytope has an exponential number of inequalities (formally, the…