6 citations · 8 across the 2 of their papers we have counts for
3 papers
cs.CG2008★ 2 cited
Improved Approximations for Guarding 1.5-Dimensional Terrains
K. Elbassioni, D. Matijevic, J. Mestre +1
We present a 4-approximation algorithm for the problem of placing a fewest guards on a 1.5D terrain so that every point of the terrain is seen by at least one guard. This improves…
cs.DS2007★ 6 cited
Lagrangian Relaxation and Partial Cover
Julián Mestre
Lagrangian relaxation has been used extensively in the design of approximation algorithms. This paper studies its strengths and limitations when applied to Partial Cover.
cs.DS2007
Weighted Popular Matchings
Julián Mestre
We study the problem of assigning jobs to applicants. Each applicant has a weight and provides a preference list ranking a subset of the jobs. A matching M is popular if there is n…