7 Search Results for "Golin, Mordecai"

Document
DOI: 10.4230/LIPIcs.FUN.2026.17
Sorting Magazines and Boxes

Authors: Gabriele Fici, Manal Mohamed, and Jakub Radoszewski

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract
It is a rainy Sunday. Agata has decided to sort the magazines on her shelf. Because the magazines are quite thin, she refuses to insert one between two others, preferring to move them only to the ends of the shelf. She has conceived a strategy for this but is unsure of its efficiency. Meanwhile, in the adjacent room, her three-year-old son, Szymon, has just finished his Montessori tower puzzle and is figuring out how to put it away. He has adopted a very intuitive approach to nesting the boxes, though he is not certain it will ultimately succeed. Agata and Szymon are employing very primitive strategies. While many sorting algorithms are remarkably simple to explain and implement-specifically, the class of in-place sorting algorithms with 𝒪(n²) worst-case and average-case running time and constant space requirements (e.g., Bubble Sort, Gnome Sort)-the strategies discussed here offer a unique perspective on "intuitive" sorting. Our contribution aims to enrich the field of simple sorting algorithms. Interestingly, determining the exact worst-case complexity of some of the proposed algorithms remains an open problem.
Cite as

Gabriele Fici, Manal Mohamed, and Jakub Radoszewski. Sorting Magazines and Boxes. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 17:1-17:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{fici_et_al:LIPIcs.FUN.2026.17,
  author =	{Fici, Gabriele and Mohamed, Manal and Radoszewski, Jakub},
  title =	{{Sorting Magazines and Boxes}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{17:1--17:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.17},
  URN =		{urn:nbn:de:0030-drops-257368},
  doi =		{10.4230/LIPIcs.FUN.2026.17},
  annote =	{Keywords: Sorting algorithm, analysis of algorithms, intuitive sorting}
}
Document
Research
DOI: 10.4230/OASIcs.Grossi.12
Encoding Data Structures for Range Queries on Arrays

Authors: Seungbum Jo and Srinivasa Rao Satti

Published in: OASIcs, Volume 132, From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday (2025)

Abstract
Efficiently processing range queries on arrays is a fundamental problem in computer science, with applications spanning diverse domains such as database management, computational biology, and geographic information systems. A range query retrieves information about a specific segment of an array, such as the sum, minimum, maximum, or median of elements within a given range. The challenge lies in designing data structures that allow such queries to be answered quickly, often in constant or logarithmic time, while keeping space overhead (and preprocessing time) small. Encoding data structures for range queries has emerged as a pivotal area of research due to the increasing demand for high-performance systems handling massive datasets. These structures consider the data together with the queries and aim to store only as much information about the data as is needed to answer the queries. The data structure does not need to access the original data to answer the queries. Encoding-based solutions often leverage techniques from succinct data structures, bit manipulation, and combinatorial optimization to achieve both space and time efficiency. By encoding the array in a manner that preserves critical information, these methods strike a balance between query time and space usage. In this survey article, we explore the landscape of encoding data structures for range queries on arrays, providing a comprehensive overview of some important results on space-efficient encodings for various types of range query.
Cite as

Seungbum Jo and Srinivasa Rao Satti. Encoding Data Structures for Range Queries on Arrays. In From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday. Open Access Series in Informatics (OASIcs), Volume 132, pp. 12:1-12:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{jo_et_al:OASIcs.Grossi.12,
  author =	{Jo, Seungbum and Satti, Srinivasa Rao},
  title =	{{Encoding Data Structures for Range Queries on Arrays}},
  booktitle =	{From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday},
  pages =	{12:1--12:12},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-391-1},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{132},
  editor =	{Conte, Alessio and Marino, Andrea and Rosone, Giovanna and Vitter, Jeffrey Scott},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Grossi.12},
  URN =		{urn:nbn:de:0030-drops-238116},
  doi =		{10.4230/OASIcs.Grossi.12},
  annote =	{Keywords: range queries, RMQ, Cartesian tree, top-k queries, range median, range mode}
}
Document
DOI: 10.4230/LIPIcs.CPM.2025.25
Encodings for Range Minimum Queries over Bounded Alphabets

Authors: Seungbum Jo and Srinivasa Rao Satti

Published in: LIPIcs, Volume 331, 36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025)

Abstract
Range minimum queries (RMQs) are fundamental operations with widespread applications in database management, text indexing and computational biology. While many space-efficient data structures have been designed for RMQs on arrays with arbitrary elements, there has not been any results developed for the case when the alphabet size is small, which is the case in many practical scenarios where RMQ structures are used. In this paper, we investigate the encoding complexity of RMQs on arrays over bounded alphabet. We consider both one-dimensional (1D) and two-dimensional (2D) arrays. For the 1D case, we present a near-optimal space encoding. For constant-sized alphabets, this also supports the queries in constant time. For the 2D case, we systematically analyze the 1-sided, 2-sided, 3-sided and 4-sided queries and derive lower bounds for encoding space, and also matching upper bounds that support efficient queries in most cases. Our results demonstrate that, even with the bounded alphabet restriction, the space requirements remain close to those for the general alphabet case.
Cite as

Seungbum Jo and Srinivasa Rao Satti. Encodings for Range Minimum Queries over Bounded Alphabets. In 36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 331, pp. 25:1-25:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{jo_et_al:LIPIcs.CPM.2025.25,
  author =	{Jo, Seungbum and Satti, Srinivasa Rao},
  title =	{{Encodings for Range Minimum Queries over Bounded Alphabets}},
  booktitle =	{36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025)},
  pages =	{25:1--25:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-369-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{331},
  editor =	{Bonizzoni, Paola and M\"{a}kinen, Veli},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2025.25},
  URN =		{urn:nbn:de:0030-drops-231198},
  doi =		{10.4230/LIPIcs.CPM.2025.25},
  annote =	{Keywords: Range minimum queries, Encoding data structures, Cartesian trees}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.35
The Expected Number of Maximal Points of the Convolution of Two 2-D Distributions

Authors: Josep Diaz and Mordecai Golin

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

Abstract
The Maximal points in a set S are those that are not dominated by any other point in S. Such points arise in multiple application settings and are called by a variety of different names, e.g., maxima, Pareto optimums, skylines. Their ubiquity has inspired a large literature on the expected number of maxima in a set S of n points chosen IID from some distribution. Most such results assume that the underlying distribution is uniform over some spatial region and strongly use this uniformity in their analysis. This research was initially motivated by the question of how this expected number changes if the input distribution is perturbed by random noise. More specifically, let B_p denote the uniform distribution from the 2-dimensional unit ball in the metric L_p. Let delta B_q denote the 2-dimensional L_q-ball, of radius delta and B_p + delta B_q be the convolution of the two distributions, i.e., a point v in B_p is reported with an error chosen from delta B_q. The question is how the expected number of maxima change as a function of delta. Although the original motivation is for small delta, the problem is well defined for any delta and our analysis treats the general case. More specifically, we study, as a function of n,delta, the expected number of maximal points when the n points in S are chosen IID from distributions of the type B_p + delta B_q where p,q in {1,2,infty} for delta > 0 and also of the type B_infty + delta B_q where q in [1,infty) for delta > 0. For fixed p,q we show that this function changes "smoothly" as a function of delta but that this smooth behavior sometimes transitions unexpectedly between different growth behaviors.
Cite as

Josep Diaz and Mordecai Golin. The Expected Number of Maximal Points of the Convolution of Two 2-D Distributions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 35:1-35:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{diaz_et_al:LIPIcs.APPROX-RANDOM.2019.35,
  author =	{Diaz, Josep and Golin, Mordecai},
  title =	{{The Expected Number of Maximal Points of the Convolution of Two 2-D Distributions}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{35:1--35:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.35},
  URN =		{urn:nbn:de:0030-drops-112501},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.35},
  annote =	{Keywords: maximal points, probabilistic geometry, perturbations, Minkowski sum}
}
Document
DOI: 10.4230/LIPIcs.ESA.2018.38
Dynamic Trees with Almost-Optimal Access Cost

Authors: Mordecai Golin, John Iacono, Stefan Langerman, J. Ian Munro, and Yakov Nekrich

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
An optimal binary search tree for an access sequence on elements is a static tree that minimizes the total search cost. Constructing perfectly optimal binary search trees is expensive so the most efficient algorithms construct almost optimal search trees. There exists a long literature of constructing almost optimal search trees dynamically, i.e., when the access pattern is not known in advance. All of these trees, e.g., splay trees and treaps, provide a multiplicative approximation to the optimal search cost. In this paper we show how to maintain an almost optimal weighted binary search tree under access operations and insertions of new elements where the approximation is an additive constant. More technically, we maintain a tree in which the depth of the leaf holding an element e_i does not exceed min(log(W/w_i),log n)+O(1) where w_i is the number of times e_i was accessed and W is the total length of the access sequence. Our techniques can also be used to encode a sequence of m symbols with a dynamic alphabetic code in O(m) time so that the encoding length is bounded by m(H+O(1)), where H is the entropy of the sequence. This is the first efficient algorithm for adaptive alphabetic coding that runs in constant time per symbol.
Cite as

Mordecai Golin, John Iacono, Stefan Langerman, J. Ian Munro, and Yakov Nekrich. Dynamic Trees with Almost-Optimal Access Cost. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 38:1-38:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{golin_et_al:LIPIcs.ESA.2018.38,
  author =	{Golin, Mordecai and Iacono, John and Langerman, Stefan and Munro, J. Ian and Nekrich, Yakov},
  title =	{{Dynamic Trees with Almost-Optimal Access Cost}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{38:1--38:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.38},
  URN =		{urn:nbn:de:0030-drops-95017},
  doi =		{10.4230/LIPIcs.ESA.2018.38},
  annote =	{Keywords: Data Structures, Binary Search Trees, Adaptive Alphabetic Coding}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2017.41
Non-approximability and Polylogarithmic Approximations of the Single-Sink Unsplittable and Confluent Dynamic Flow Problems

Authors: Mordecai J. Golin, Hadi Khodabande, and Bo Qin

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract
Dynamic Flows were introduced by Ford and Fulkerson in 1958 to model flows over time. They define edge capacities to be the total amount of flow that can enter an edge in one time unit. Each edge also has a length, representing the time needed to traverse it. Dynamic Flows have been used to model many problems including traffic congestion, hop-routing of packets and evacuation protocols in buildings. While the basic problem of moving the maximal amount of supplies from sources to sinks is polynomial time solvable, natural minor modifications can make it NP-hard. One such modification is that flows be confluent, i.e., all flows leaving a vertex must leave along the same edge. This corresponds to natural conditions in, e.g., evacuation planning and hop routing. We investigate the single-sink Confluent Quickest Flow problem. The input is a graph with edge capacities and lengths, sources with supplies and a sink. The problem is to find a confluent flow minimizing the time required to send supplies to the sink. Our main results include: a) Logarithmic Non-Approximability: Directed Confluent Quickest Flows cannot be approximated in polynomial time with an O(\log n) approximation factor, unless P=NP. b) Polylogarithmic Bicriteria Approximations: Polynomial time (O(\log^8 n), O(\log^2 \kappa)) bicritera approximation algorithms for the Confluent Quickest Flow problem where \kappa is the number of sinks, in both directed and undirected graphs. Corresponding results are also developed for the Confluent Maximum Flow over time problem. The techniques developed also improve recent approximation algorithms for static confluent flows.
Cite as

Mordecai J. Golin, Hadi Khodabande, and Bo Qin. Non-approximability and Polylogarithmic Approximations of the Single-Sink Unsplittable and Confluent Dynamic Flow Problems. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 41:1-41:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{golin_et_al:LIPIcs.ISAAC.2017.41,
  author =	{Golin, Mordecai J. and Khodabande, Hadi and Qin, Bo},
  title =	{{Non-approximability and Polylogarithmic Approximations of the Single-Sink Unsplittable and Confluent Dynamic Flow Problems}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{41:1--41:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.41},
  URN =		{urn:nbn:de:0030-drops-82435},
  doi =		{10.4230/LIPIcs.ISAAC.2017.41},
  annote =	{Keywords: Optimization, Approximation, Dynamic Flow, Confluent Flow}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2016.25
Sink Evacuation on Trees with Dynamic Confluent Flows

Authors: Di Chen and Mordecai Golin

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

Abstract
Let G = (V, E) be a graph modelling a building or road network in which edges have-both travel times (lengths) and capacities associated with them. An edge’s capacity is the number of people that can enter that edge in a unit of time. In emergencies, people evacuate towards the exits. If too many people try to evacuate through the same edge, congestion builds up and slows down the evacuation. Graphs with both lengths and capacities are known as Dynamic Flow networks. An evacuation plan for G consists of a choice of exit locations and a partition of the people at the vertices into groups, with each group evacuating to the same exit. The evacuation time of a plan is the time it takes until the last person evacuates. The k-sink evacuation problem is to provide an evacuation plan with k exit locations that minimizes the evacuation time. It is known that this problem is NP-Hard for general graphs but no polynomial time algorithm was previously known even for the case of G a tree. This paper presents an O(nk^2 log^5 n) algorithm for the k-sink evacuation problem on trees, which can also be applied to a more general class of problems.
Cite as

Di Chen and Mordecai Golin. Sink Evacuation on Trees with Dynamic Confluent Flows. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 25:1-25:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ISAAC.2016.25,
  author =	{Chen, Di and Golin, Mordecai},
  title =	{{Sink Evacuation on Trees with Dynamic Confluent Flows}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{25:1--25:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.25},
  URN =		{urn:nbn:de:0030-drops-67951},
  doi =		{10.4230/LIPIcs.ISAAC.2016.25},
  annote =	{Keywords: Sink Evacuation, Dynamic Flow, Facility Location, Parametric Search}
}
  • Refine by Type
  • 7 Document/PDF
  • 3 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 2 2025
  • 1 2019
  • 1 2018
  • 1 2017
  • Show More...

  • Refine by Author
  • 3 Golin, Mordecai
  • 2 Jo, Seungbum
  • 2 Satti, Srinivasa Rao
  • 1 Chen, Di
  • 1 Diaz, Josep
  • Show More...

  • Refine by Series/Journal
  • 6 LIPIcs
  • 1 OASIcs

  • Refine by Classification
  • 3 Theory of computation → Data structures design and analysis
  • 1 Theory of computation → Randomness, geometry and discrete structures
  • 1 Theory of computation → Sorting and searching

  • Refine by Keyword
  • 2 Dynamic Flow
  • 1 Adaptive Alphabetic Coding
  • 1 Approximation
  • 1 Binary Search Trees
  • 1 Cartesian tree
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact