211 citations · 504 across the 42 of their papers we have counts for
5 papers · 1 filter
Threshold Rounding for the Standard LP Relaxation of some Geometric Stabbing Problems
Khaled Elbassioni, Saurabh Ray
In the rectangle stabbing problem, we are given a set $\cR$ of axis-aligned rectangles in $\RR^2$, and the objective is to find a minimum-cardinality set of horizontal and/or verti…
Finding Small Hitting Sets in Infinite Range Spaces of Bounded VC-dimension
Khaled Elbassioni
We consider the problem of finding a small hitting set in an {\it infinite} range space $\cF=(Q,\cR)$ of bounded VC-dimension. We show that, under reasonably general assumptions, t…
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…
On Computing the Vertex Centroid of a Polyhedron
Khaled Elbassioni, Hans Raj Tiwary
Let be an -polytope in with vertex set . The vertex centroid is defined as the average of the vertices in . We prove that computing…
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…