11 citations · 15 across the 10 of their papers we have counts for
11 papers
Localized versions of extremal problems
David Malec, Casey Tompkins
We generalize several classical theorems in extremal combinatorics by replacing a global constraint with an inequality which holds for all objects in a given class. In particular w…
Saturation problems in the Ramsey theory of graphs, posets and point sets
Gábor Damásdi, Balázs Keszegh, David Malec +3
In 1964, Erdős, Hajnal and Moon introduced a saturation version of Turán's classical theorem in extremal graph theory. In particular, they determined the minimum number of edges in…
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…
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…
How to Influence People with Partial Incentives
Erik D. Demaine, MohammadTaghi Hajiaghayi, Hamid Mahini +4
We study the power of fractional allocations of resources to maximize influence in a network. This work extends in a natural way the well-studied model by Kempe, Kleinberg, and Tar…
Prior-Independent Mechanisms for Scheduling
Shuchi Chawla, Jason D. Hartline, David Malec +1
We study the makespan minimization problem with unrelated selfish machines under the assumption that job sizes are stochastic. We design simple truthful mechanisms that under vario…