3 papers
cs.DS2015
Approximate Deadline-Scheduling with Precedence Constraints
Hossein Efsandiari, MohammadTaghi Hajiaghyi, Jochen Koenemann +3
We consider the classic problem of scheduling a set of n jobs non-preemptively on a single machine. Each job j has non-negative processing time, weight, and deadline, and a feasibl…
math.CO2015
De Bruijn-Erdős type theorems for graphs and posets
Pierre Aboulker, Guillaume Lagarde, David Malec +2
A classical theorem of De Bruijn and Erdős asserts that any noncollinear set of n points in the plane determines at least n distinct lines. We prove that an analogue of this theore…
cs.GT2010
The power of randomness in Bayesian optimal mechanism design
Shuchi Chawla, David Malec, Balasubramanian Sivan
We investigate the power of randomness in the context of a fundamental Bayesian optimal mechanism design problem--a single seller aims to maximize expected revenue by allocating mu…