Deterministic algorithms for 2-d convex programming and 3-d online linear programming

Research output: Contribution to conferencePaperpeer-review

Abstract

We present a deterministic algorithm for solving two-dimensional convex programs with a linear objective function. The algorithm requires O(k log k) primitive operations for k constraints; if a feasible point is given, the bound reduces to O(k log k/log log k). As a consequence, we can decide whether k convex n-gons in the plane have a common intersection in O(k log n min{log k, log log n}) worst-case time. Furthermore, we can solve the three-dimensional online linear programming problem in o(log3 n) worst-case time per operation.

Original languageEnglish (US)
Pages464-472
Number of pages9
StatePublished - Jan 1 1997
Externally publishedYes
EventProceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, LA, USA
Duration: Jan 5 1997Jan 7 1997

Other

OtherProceedings of the 1996 8th Annual ACM-SIAM Symposium on Discrete Algorithms
CityNew Orleans, LA, USA
Period1/5/971/7/97

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Deterministic algorithms for 2-d convex programming and 3-d online linear programming'. Together they form a unique fingerprint.

Cite this