Small-dimensional linear programming and convex hulls made easy |
| |
Authors: | Raimund Seidel |
| |
Institution: | (1) Computer Science Division, University of California at Berkeley, 94720 Berkeley, CA, USA |
| |
Abstract: | We present two randomized algorithms. One solves linear programs involvingm constraints ind variables in expected timeO(m). The other constructs convex hulls ofn points in ℝ
d
,d>3, in expected timeO(n
d/2]). In both boundsd is considered to be a constant. In the linear programming algorithm the dependence of the time bound ond is of the formd!. The main virtue of our results lies in the utter simplicity of the algorithms as well as their analyses.
Large portions of the research reported here were conducted while the author visited DIMACS at Princeton University. The author
was supported by NSF Presidential Young Investigator Award CCR-9058440. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|