Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor

Author(s):

Ramos, Edgar A.

dblp



Editor(s):





BibTeX cite key*:

Ramos2000d

Title, Booktitle

Title*:

Linear Programming Queries Revisited

Booktitle*:

Proceedings of the 16th Annual Symposium on Computational Geometry (SCG-00)

Event, URLs

URL of the conference:

http://www.cs.ust.hk/tcsc/scg00.html

URL for downloading the paper:

http://www.mpi-sb.mpg.de/~ramos

Event Address*:

Clear Water Bay, Kowloon, Hong Kong

Language:

English

Event Date*
(no longer used):

June 12-14, 2000

Organization:

Association of Computing Machinery (ACM)

Event Start Date:

12 June 2000

Event End Date:

14 June 2000

Publisher

Name*:

ACM Press

URL:


Address*:

New York, USA

Type:


Vol, No, Year, pp.

Series:


Volume:


Number:


Month:

June

Pages:

176-181

Year*:

2000

VG Wort Pages:


ISBN/ISSN:


Sequence Number:


DOI:




Note, Abstract, ©


(LaTeX) Abstract:

We describe an approach for answering linear programming queries with respect to
a set of $n$ linear constraints in $\Re^d$, for a fixed dimension $d$. Solutions
to this problem had been given before by Matou\v{s}ek (1993) using a multidimesional
version of parametric search and by Chan (1996) using randomization and Clarkson's
approach to linear programming. These previous approaches use data structures for
halfspace-range emptiness queries and reporting queries, respectively. Our approach
is a generalization of Chan's: it also uses halfspace-range reporting data structures,
Clarkson's approach to linear programming, and avoids parametric search; unlike
Chan's appraoch, it gives deterministic solutions without considerable additional
preprocessing overhead.
The new solution is as good or improves the previous solutions in all the range of
storage space: with $O(n^{\fdh} \log^{O(1)} n)$ storage space, it achieves query time
$O(\log^{ c \log d} n)$, where $c$ is a small constant independent from $d$, in
comparison to $O(\log^{d+1} n)$ for Matou\v{s}ek's data structure and $O(n^{c'\log d})$
for Chan's; with $O(n)$ storage space, it achieves, as Chan's data structure, query time
$O(n^{1-\ifdh} 2^{O(\log^* n)})$ after $O(n^{1+\epsilon})$ preprocessing, but
without using randomization.



Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

Expert

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Ramos2000d,
AUTHOR = {Ramos, Edgar A.},
TITLE = {Linear Programming Queries Revisited},
BOOKTITLE = {Proceedings of the 16th Annual Symposium on Computational Geometry (SCG-00)},
PUBLISHER = {ACM Press},
YEAR = {2000},
ORGANIZATION = {Association of Computing Machinery (ACM)},
PAGES = {176--181},
ADDRESS = {Clear Water Bay, Kowloon, Hong Kong},
MONTH = {June},
}


Entry last modified by Uwe Brahm, 03/02/2010
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Edgar A. Ramos
Created
02/23/2001 05:26:17 PM
Revisions
4.
3.
2.
1.
0.
Editor(s)
Uwe Brahm
Anja Becker
Anja Becker
Anja Becker
Anja Becker
Edit Dates
02/14/2005 09:32:49 PM
20.03.2001 17:05:12
20.03.2001 15:53:33
14.03.2001 14:08:12
23/02/2001 17:26:17
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section