7 citations · 11 across the 16 of their papers we have counts for
4 papers · 1 filter
Stabbing Planes
Paul Beame, Noah Fleming, Russell Impagliazzo +4
We develop a new semi-algebraic proof system called Stabbing Planes which formalizes modern branch-and-cut algorithms for integer programming and is in the style of DPLL-based mode…
A Simple PTAS for the Dual Bin Packing Problem and Advice Complexity of Its Online Version
Allan Borodin, Denis Pankratov, Amirali Salehi-Abari
Recently, Renault (2016) studied the dual bin packing problem in the per-request advice model of online algorithms. He showed that given advice bits for each input item al…
On Conceptually Simple Algorithms for Variants of Online Bipartite Matching
Allan Borodin, Denis Pankratov, Amirali Salehi-Abari
We present a series of results regarding conceptually simple algorithms for bipartite matching in various online and related models. We first consider a deterministic adversarial m…
Random CNFs are Hard for Cutting Planes
Noah Fleming, Denis Pankratov, Toniann Pitassi +1
The random k-SAT model is the most important and well-studied distribution over k-SAT instances. It is closely connected to statistical physics; it is used as a testbench for satis…