| Presentation | 2010-03-12 Deterministic Constant-Working-Space Algorithms for two dimensional Linear Programming Tetsuo ASANO, Danny Z. CHEN, Takeshi TOKUYAMA, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | This paper presents a space-efficient algorithm for Linear Programming of two variables. It runs in O(n^<1+ε>) time using working space O(1/ε) for any small constant ε>0. What is interesting is the effect of randomness to computation; indeed, if we allow randomization, the running time is improved to O(n log n) easily. We will also mention related earlier work on stream algorithms by Chan and Chen in the talk. This article is a technical report without peer review, and its polished version will be published elsewhere. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | constant memory algorithm / computational geometry / linear programming |
| Paper # | COMP2009-52 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2010/3/5(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Deterministic Constant-Working-Space Algorithms for two dimensional Linear Programming |
| Sub Title (in English) | |
| Keyword(1) | constant memory algorithm |
| Keyword(2) | computational geometry |
| Keyword(3) | linear programming |
| 1st Author's Name | Tetsuo ASANO |
| 1st Author's Affiliation | Graduate School of Information Sciences, JAIST() |
| 2nd Author's Name | Danny Z. CHEN |
| 2nd Author's Affiliation | Department of CS and Engineering, University of Notre Dame |
| 3rd Author's Name | Takeshi TOKUYAMA |
| 3rd Author's Affiliation | Graduate School of Information Sciences, Tohoku University |
| Date | 2010-03-12 |
| Paper # | COMP2009-52 |
| Volume (vol) | vol.109 |
| Number (no) | 465 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |