2 citations · 4 across the 5 of their papers we have counts for
6 papers
On the Complexity of Polytopes in
Komei Fukuda, May Szedlak
In this paper we consider polytopes given by systems of inequalities in variables, where every inequality has at most two variables with nonzero coefficient. We denote this…
On the Existence of Ordinary Triangles
Radoslav Fulek, Hossein Nassajian Mojarrad, Márton Naszódi +3
Let be a finite point set in the plane. A \emph{-ordinary triangle} in is a subset of consisting of three non-collinear points such that each of the three lines dete…
Redundancies in Linear Systems with two Variables per Inequality
Komei Fukuda, May Szedlak
The problem of detecting and removing redundant constraints is fundamental in optimization. We focus on the case of linear programs (LPs), given by variables with inequalit…
Random Sampling with Removal
Kenneth L. Clarkson, Bernd Gärtner, Johannes Lengler +1
We study randomized algorithms for constrained optimization, in abstract frameworks that include, in strictly increasing generality: convex programming; LP-type problems; violator…
Combinatorial Redundancy Detection
Komei Fukuda, Bernd Gärtner, May Szedlák
The problem of detecting and removing redundant constraints is fundamental in optimization. We focus on the case of linear programs (LPs) in dictionary form, given by equality…
Higher Dimensional Discrete Cheeger Inequalities
Anna Gundert, May Szedlák
For graphs there exists a strong connection between spectral and combinatorial expansion properties. This is expressed, e.g., by the discrete Cheeger inequality, the lower bound of…