2 Search Results for "Tangwongsan, Kanat"


Document
Track A: Algorithms, Complexity and Games
The Geometry of Tree-Based Sorting

Authors: Guy E. Blelloch and Magdalen Dobson

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)


Abstract
We study the connections between sorting and the binary search tree (BST) model, with an aim towards showing that the fields are connected more deeply than is currently appreciated. While any BST can be used to sort by inserting the keys one-by-one, this is a very limited relationship and importantly says nothing about parallel sorting. We show what we believe to be the first formal relationship between the BST model and sorting. Namely, we show that a large class of sorting algorithms, which includes mergesort, quicksort, insertion sort, and almost every instance-optimal sorting algorithm, are equivalent in cost to offline BST algorithms. Our main theoretical tool is the geometric interpretation of the BST model introduced by Demaine et al. [Demaine et al., 2009], which finds an equivalence between searches on a BST and point sets in the plane satisfying a certain property. To give an example of the utility of our approach, we introduce the log-interleave bound, a measure of the information-theoretic complexity of a permutation π, which is within a lg lg n multiplicative factor of a known lower bound in the BST model; we also devise a parallel sorting algorithm with polylogarithmic span that sorts a permutation π using comparisons proportional to its log-interleave bound. Our aforementioned result on sorting and offline BST algorithms can be used to show existence of an offline BST algorithm whose cost is within a constant factor of the log-interleave bound of any permutation π.

Cite as

Guy E. Blelloch and Magdalen Dobson. The Geometry of Tree-Based Sorting. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 26:1-26:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{blelloch_et_al:LIPIcs.ICALP.2023.26,
  author =	{Blelloch, Guy E. and Dobson, Magdalen},
  title =	{{The Geometry of Tree-Based Sorting}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{26:1--26:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.26},
  URN =		{urn:nbn:de:0030-drops-180780},
  doi =		{10.4230/LIPIcs.ICALP.2023.26},
  annote =	{Keywords: binary search trees, sorting, dynamic optimality, parallelism}
}
Document
All-Norms and All-L_p-Norms Approximation Algorithms

Authors: Daniel Golovin, Anupam Gupta, Amit Kumar, and Kanat Tangwongsan

Published in: LIPIcs, Volume 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2008)


Abstract
In many optimization problems, a solution can be viewed as ascribing a ``cost\'\' to each client, and the goal is to optimize some aggregation of the per-client costs. We often optimize some $L_p$-norm (or some other symmetric convex function or norm) of the vector of costs---though different applications may suggest different norms to use. Ideally, we could obtain a solution that optimizes several norms simultaneously. In this paper, we examine approximation algorithms that simultaneously perform well on all norms, or on all $L_p$ norms. A natural problem in this framework is the $L_p$ Set Cover problem, which generalizes \textsc{Set Cover} and \textsc{Min-Sum Set Cover}. We show that the greedy algorithm \emph{simultaneously gives a $(p + \ln p + O(1))$-approximation for all $p$, and show that this approximation ratio is optimal up to constants} under reasonable complexity-theoretic assumptions. We additionally show how to use our analysis techniques to give similar results for the more general \emph{submodular set cover}, and prove some results for the so-called \emph{pipelined set cover} problem. We then go on to examine approximation algorithms in the ``all-norms\'\' and the ``all-$L_p$-norms\'\' frameworks more broadly, and present algorithms and structural results for other problems such as $k$-facility-location, TSP, and average flow-time minimization, extending and unifying previously known results.

Cite as

Daniel Golovin, Anupam Gupta, Amit Kumar, and Kanat Tangwongsan. All-Norms and All-L_p-Norms Approximation Algorithms. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 2, pp. 199-210, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{golovin_et_al:LIPIcs.FSTTCS.2008.1753,
  author =	{Golovin, Daniel and Gupta, Anupam and Kumar, Amit and Tangwongsan, Kanat},
  title =	{{All-Norms and All-L\underlinep-Norms Approximation Algorithms}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{199--210},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-08-8},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{2},
  editor =	{Hariharan, Ramesh and Mukund, Madhavan and Vinay, V},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2008.1753},
  URN =		{urn:nbn:de:0030-drops-17537},
  doi =		{10.4230/LIPIcs.FSTTCS.2008.1753},
  annote =	{Keywords: Approximation algorithms, set-cover problems, combinatorial optimization, sampling minkowski norms}
}
  • Refine by Author
  • 1 Blelloch, Guy E.
  • 1 Dobson, Magdalen
  • 1 Golovin, Daniel
  • 1 Gupta, Anupam
  • 1 Kumar, Amit
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Sorting and searching

  • Refine by Keyword
  • 1 Approximation algorithms
  • 1 binary search trees
  • 1 combinatorial optimization
  • 1 dynamic optimality
  • 1 parallelism
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2008
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail