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.CC2008
Characterization of the Vertices and Extreme Directions of the Negative Cycles Polyhedron and Hardness of Generating Vertices of 0/1-Polyhedra
Endre Boros, Khaled Elbassioni, Vladimir Gurvich +1
Given a graph and a weight function on the edges $w:E\mapsto\RR$, we consider the polyhedron of negative-weight flows on , and get a complete characterization…
cs.CG2005
Upper Bound on the Number of Vertices of Polyhedra with -Constraint Matrices
Khaled Elbassioni, Zvi Lotker, Raimund Seidel
In this note we show that the maximum number of vertices in any polyhedron with -constraint matrix and a real vector is at most $d…