DROPS

Document

APPROX

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.12

Relational Approximations for Subspace Primitives

Authors: Xiang Liu and Kasturi Varadarajan

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

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.

Cite as

Xiang Liu and Kasturi Varadarajan. Relational Approximations for Subspace Primitives. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{liu_et_al:LIPIcs.APPROX/RANDOM.2025.12,
  author =	{Liu, Xiang and Varadarajan, Kasturi},
  title =	{{Relational Approximations for Subspace Primitives}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{12:1--12:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.12},
  URN =		{urn:nbn:de:0030-drops-243781},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.12},
  annote =	{Keywords: relational algorithm, Euclidean distance, subspace approximation}
}

Search Results

Documents authored by Liu, Xiang

Relational Approximations for Subspace Primitives

Abstract

Cite as

Thanks for your feedback!

Could not send message