4 Search Results for "Golin, Mordecai"

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-dev.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-dev.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-dev.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-dev.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 Author
  • 3 Golin, Mordecai
  • 1 Chen, Di
  • 1 Diaz, Josep
  • 1 Golin, Mordecai J.
  • 1 Iacono, John
  • Show More...

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

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

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 1 2016
  • 1 2017
  • 1 2018
  • 1 2019

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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact