Conference proceeding
Relational Approximations for Subspace Primitives
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2025, Vol.353, 12
09/15/2025
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.12
Abstract
We explore fundamental geometric computations on point sets that are given to the algorithm implicitly. In particular, we are given a database which is a collection of tables with numerical values, and the geometric computation is to be performed on the join of the tables. Explicitly computing this join takes time exponential in the size of the tables. We are therefore interested in geometric problems that can be solved by algorithms whose running time is a polynomial in the size of the tables. Such relational algorithms are typically not able to explicitly compute the join.
To avoid the NP-completeness bottleneck, researchers assume that the tables have a tractable combinatorial structure, like being acyclic. Even with this assumption, simple geometric computations turn out to be non-trivial and sometimes intractable. In this article, we study the problem of computing the maximum distance of a point in the join to a given subspace, and develop approximation algorithms for this NP-hard problem.
Details
- Title: Subtitle
- Relational Approximations for Subspace Primitives
- Creators
- Xiang Liu - Department of Computer Science, University of Iowa, Iowa City, IA, United StatesKasturi Varadarajan - University of Iowa
- Resource Type
- Conference proceeding
- Publication Details
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2025, Vol.353, 12
- DOI
- 10.4230/LIPIcs.APPROX/RANDOM.2025.12
- ISSN
- 1868-8969
- Language
- English
- Date published
- 09/15/2025
- Academic Unit
- Computer Science
- Record Identifier
- 9985024248802771
Metrics
1 Record Views