13 Search Results for "Rawitz, Dror"

Document
DOI: 10.4230/LIPIcs.MFCS.2022.13
Graph Realization of Distance Sets

Authors: Amotz Bar-Noy, David Peleg, Mor Perry, and Dror Rawitz

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract
The Distance Realization problem is defined as follows. Given an n × n matrix D of nonnegative integers, interpreted as inter-vertex distances, find an n-vertex weighted or unweighted graph G realizing D, i.e., whose inter-vertex distances satisfy dist_G(i,j) = D_{i,j} for every 1 ≤ i < j ≤ n, or decide that no such realizing graph exists. The problem was studied for general weighted and unweighted graphs, as well as for cases where the realizing graph is restricted to a specific family of graphs (e.g., trees or bipartite graphs). An extension of Distance Realization that was studied in the past is where each entry in the matrix D may contain a range of consecutive permissible values. We refer to this extension as Range Distance Realization (or Range-DR). Restricting each range to at most k values yields the problem k-Range Distance Realization (or k-Range-DR). The current paper introduces a new extension of Distance Realization, in which each entry D_{i,j} of the matrix may contain an arbitrary set of acceptable values for the distance between i and j, for every 1 ≤ i < j ≤ n. We refer to this extension as Set Distance Realization (Set-DR), and to the restricted problem where each entry may contain at most k values as k-Set Distance Realization (or k-Set-DR). We first show that 2-Range-DR is NP-hard for unweighted graphs (implying the same for 2-Set-DR). Next we prove that 2-Set-DR is NP-hard for unweighted and weighted trees. We then explore Set-DR where the realization is restricted to the families of stars, paths, or cycles. For the weighted case, our positive results are that for each of these families there exists a polynomial time algorithm for 2-Set-DR. On the hardness side, we prove that 6-Set-DR is NP-hard for stars and 5-Set-DR is NP-hard for paths and cycles. For the unweighted case, our results are the same, except for the case of unweighted stars, for which k-Set-DR is polynomially solvable for any k.
Cite as

Amotz Bar-Noy, David Peleg, Mor Perry, and Dror Rawitz. Graph Realization of Distance Sets. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 13:1-13:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{barnoy_et_al:LIPIcs.MFCS.2022.13,
  author =	{Bar-Noy, Amotz and Peleg, David and Perry, Mor and Rawitz, Dror},
  title =	{{Graph Realization of Distance Sets}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{13:1--13:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.13},
  URN =		{urn:nbn:de:0030-drops-168119},
  doi =		{10.4230/LIPIcs.MFCS.2022.13},
  annote =	{Keywords: Graph Realization, distance realization, network design}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2022.14
On the Role of the High-Low Partition in Realizing a Degree Sequence by a Bipartite Graph

Authors: Amotz Bar-Noy, Toni Böhnlein, David Peleg, and Dror Rawitz

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract
We consider the problem of characterizing degree sequences that can be realized by a bipartite graph. If a partition of the sequence into the two sides of the bipartite graph is given as part of the input, then a complete characterization has been established over 60 years ago. However, the general question, in which a partition and a realizing graph need to be determined, is still open. We investigate the role of an important class of special partitions, called High-Low partitions, which separate the degrees of a sequence into two groups, the high degrees and the low degrees. We show that when the High-Low partition exists and satisfies some natural properties, analysing the High-Low partition resolves the bigraphic realization problem. For sequences that are known to be not realizable by a bipartite graph or that are undecided, we provide approximate realizations based on the High-Low partition.
Cite as

Amotz Bar-Noy, Toni Böhnlein, David Peleg, and Dror Rawitz. On the Role of the High-Low Partition in Realizing a Degree Sequence by a Bipartite Graph. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 14:1-14:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{barnoy_et_al:LIPIcs.MFCS.2022.14,
  author =	{Bar-Noy, Amotz and B\"{o}hnlein, Toni and Peleg, David and Rawitz, Dror},
  title =	{{On the Role of the High-Low Partition in Realizing a Degree Sequence by a Bipartite Graph}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{14:1--14:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.14},
  URN =		{urn:nbn:de:0030-drops-168121},
  doi =		{10.4230/LIPIcs.MFCS.2022.14},
  annote =	{Keywords: Graph Realization, Bipartite Graphs, Degree Sequences, Graphic Sequences, Bigraphic Sequences, Approximate Realization, Multigraph Realization}
}
Document
Invited Paper
DOI: 10.4230/LIPIcs.SWAT.2022.1
On Realizing a Single Degree Sequence by a Bipartite Graph (Invited Paper)

Authors: Amotz Bar-Noy, Toni Böhnlein, David Peleg, and Dror Rawitz

Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)

Abstract
This paper addresses the classical problem of characterizing degree sequences that can be realized by a bipartite graph. For the simpler variant of the problem, where a partition of the sequence into the two sides of the bipartite graph is given as part of the input, a complete characterization was given by Gale and Ryser over 60 years ago. However, the general question, in which both the partition and the realizing graph need to be determined, is still open. This paper provides an overview of some of the known results on this problem in interesting special cases, including realizations by bipartite graphs and bipartite multigraphs.
Cite as

Amotz Bar-Noy, Toni Böhnlein, David Peleg, and Dror Rawitz. On Realizing a Single Degree Sequence by a Bipartite Graph (Invited Paper). In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 1:1-1:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{barnoy_et_al:LIPIcs.SWAT.2022.1,
  author =	{Bar-Noy, Amotz and B\"{o}hnlein, Toni and Peleg, David and Rawitz, Dror},
  title =	{{On Realizing a Single Degree Sequence by a Bipartite Graph}},
  booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
  pages =	{1:1--1:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-236-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{227},
  editor =	{Czumaj, Artur and Xin, Qin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.1},
  URN =		{urn:nbn:de:0030-drops-161618},
  doi =		{10.4230/LIPIcs.SWAT.2022.1},
  annote =	{Keywords: Degree Sequences, Graph Realization, Bipartite Graphs, Graphic Sequences, Bigraphic Sequences, Multigraph Realization}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.27
Selected Neighbor Degree Forest Realization

Authors: Amotz Bar-Noy, David Peleg, Dror Rawitz, and Elad Yehezkel

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
The classical degree realization problem is defined as follows: Given a sequence d̄ = (d_1,…,d_n) of positive integers, construct an n-vertex graph in which each vertex u_i has degree d_i (or decide that no such graph exists). In this article, we present and study the related selected neighbor degree realization problem, which requires that each vertex u_i of G has a neighbor of degree d_i. We solve the problem when G is required to be acyclic (i.e., a forest), and present a sufficient and necessary condition for a given sequence to be realizable.
Cite as

Amotz Bar-Noy, David Peleg, Dror Rawitz, and Elad Yehezkel. Selected Neighbor Degree Forest Realization. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 27:1-27:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{barnoy_et_al:LIPIcs.ISAAC.2021.27,
  author =	{Bar-Noy, Amotz and Peleg, David and Rawitz, Dror and Yehezkel, Elad},
  title =	{{Selected Neighbor Degree Forest Realization}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{27:1--27:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.27},
  URN =		{urn:nbn:de:0030-drops-154609},
  doi =		{10.4230/LIPIcs.ISAAC.2021.27},
  annote =	{Keywords: network realization, graph algorithms, lower bound}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.10
Minimum Neighboring Degree Realization in Graphs and Trees

Authors: Amotz Bar-Noy, Keerti Choudhary, Avi Cohen, David Peleg, and Dror Rawitz

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
We study a graph realization problem that pertains to degrees in vertex neighborhoods. The classical problem of degree sequence realizability asks whether or not a given sequence of n positive integers is equal to the degree sequence of some n-vertex undirected simple graph. While the realizability problem of degree sequences has been well studied for different classes of graphs, there has been relatively little work concerning the realizability of other types of information profiles, such as the vertex neighborhood profiles. In this paper we introduce and explore the minimum degrees in vertex neighborhood profile as it is one of the most natural extensions of the classical degree profile to vertex neighboring degree profiles. Given a graph G = (V,E), the min-degree of a vertex v ∈ V, namely MinND(v), is given by min{deg(w) ∣ w ∈ N[v]}. Our input is a sequence σ = (d_𝓁^{n_𝓁}, ⋯ , d₁^{n₁}), where d_{i+1} > d_i and each n_i is a positive integer. We provide some necessary and sufficient conditions for σ to be realizable. Furthermore, under the restriction that the realization is acyclic, i.e., a tree or a forest, we provide a full characterization of realizable sequences, along with a corresponding constructive algorithm. We believe our results are a crucial step towards understanding extremal neighborhood degree relations in graphs.
Cite as

Amotz Bar-Noy, Keerti Choudhary, Avi Cohen, David Peleg, and Dror Rawitz. Minimum Neighboring Degree Realization in Graphs and Trees. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 10:1-10:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{barnoy_et_al:LIPIcs.ESA.2020.10,
  author =	{Bar-Noy, Amotz and Choudhary, Keerti and Cohen, Avi and Peleg, David and Rawitz, Dror},
  title =	{{Minimum Neighboring Degree Realization in Graphs and Trees}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{10:1--10:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.10},
  URN =		{urn:nbn:de:0030-drops-128765},
  doi =		{10.4230/LIPIcs.ESA.2020.10},
  annote =	{Keywords: Graph realization, neighborhood profile, graph algorithms, degree sequences}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2020.10
Graph Realizations: Maximum Degree in Vertex Neighborhoods

Authors: Amotz Bar-Noy, Keerti Choudhary, David Peleg, and Dror Rawitz

Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)

Abstract
The classical problem of degree sequence realizability asks whether or not a given sequence of n positive integers is equal to the degree sequence of some n-vertex undirected simple graph. While the realizability problem of degree sequences has been well studied for different classes of graphs, there has been relatively little work concerning the realizability of other types of information profiles, such as the vertex neighborhood profiles. In this paper, we initiate the study of neighborhood degree profiles, wherein, our focus is on the natural problem of realizing maximum neighborhood degrees. More specifically, we ask the following question: "Given a sequence D of n non-negative integers 0≤ d₁≤ ⋯ ≤ d_n, does there exist a simple graph with vertices v₁,…, v_n such that for every 1≤ i ≤ n, the maximum degree in the neighborhood of v_i is exactly d_i?" We provide in this work various results for maximum-neighborhood-degree for general n vertex graphs. Our results are first of its kind that studies extremal neighborhood degree profiles. For closed as well as open neighborhood degree profiles, we provide a complete realizability criteria. We also provide tight bounds for the number of maximum neighbouring degree profiles of length n that are realizable. Our conditions are verifiable in linear time and our realizations can be constructed in polynomial time.
Cite as

Amotz Bar-Noy, Keerti Choudhary, David Peleg, and Dror Rawitz. Graph Realizations: Maximum Degree in Vertex Neighborhoods. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{barnoy_et_al:LIPIcs.SWAT.2020.10,
  author =	{Bar-Noy, Amotz and Choudhary, Keerti and Peleg, David and Rawitz, Dror},
  title =	{{Graph Realizations: Maximum Degree in Vertex Neighborhoods}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{10:1--10:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-150-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{162},
  editor =	{Albers, Susanne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.10},
  URN =		{urn:nbn:de:0030-drops-122572},
  doi =		{10.4230/LIPIcs.SWAT.2020.10},
  annote =	{Keywords: Graph realization, neighborhood profile, extremum-degree}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.42
The Generalized Microscopic Image Reconstruction Problem

Authors: Amotz Bar-Noy, Toni Böhnlein, Zvi Lotker, David Peleg, and Dror Rawitz

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract
This paper presents and studies a generalization of the microscopic image reconstruction problem (MIR) introduced by Frosini and Nivat [Andrea Frosini and Maurice Nivat, 2007; Nivat, 2002]. Consider a specimen for inspection, represented as a collection of points typically organized on a grid in the plane. Assume each point x has an associated physical value l_x, which we would like to determine. However, it might be that obtaining these values precisely (by a surgical probe) is difficult, risky, or impossible. The alternative is to employ aggregate measuring techniques (such as EM, CT, US or MRI), whereby each measurement is taken over a larger window, and the exact values at each point are subsequently extracted by computational methods. In this paper we extend the MIR framework in a number of ways. First, we consider a generalized setting where the inspected object is represented by an arbitrary graph G, and the vector l in R^n assigns a value l_v to each node v. A probe centered at a vertex v will capture a window encompassing its entire neighborhood N[v], i.e., the outcome of a probe centered at v is P_v = sum_{w in N[v]} l_w. We give a criterion for the graphs for which the extended MIR problem can be solved by extracting the vector l from the collection of probes, P^- = {P_v | v in V}. We then consider cases where such reconstruction is impossible (namely, graphs G for which the probe vector P is inconclusive, in the sense that there may be more than one vector l yielding P). Let us assume that surgical probes (whose outcome at vertex v is the exact value of l_v) are technically available to us (yet are expensive or risky, and must be used sparingly). We show that in such cases, it may still be possible to achieve reconstruction based on a combination of a collection of standard probes together with a suitable set of surgical probes. We aim at identifying the minimum number of surgical probes necessary for a unique reconstruction, depending on the graph topology. This is referred to as the Minimum Surgical Probing problem (MSP). Besides providing a solution for the above problems for arbitrary graphs, we also explore the range of possible behaviors of the Minimum Surgical Probing problem by determining the number of surgical probes necessary in certain specific graph families, such as perfect k-ary trees, paths, cycles, grids, tori and tubes.
Cite as

Amotz Bar-Noy, Toni Böhnlein, Zvi Lotker, David Peleg, and Dror Rawitz. The Generalized Microscopic Image Reconstruction Problem. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 42:1-42:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{barnoy_et_al:LIPIcs.ISAAC.2019.42,
  author =	{Bar-Noy, Amotz and B\"{o}hnlein, Toni and Lotker, Zvi and Peleg, David and Rawitz, Dror},
  title =	{{The Generalized Microscopic Image Reconstruction Problem}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{42:1--42:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.42},
  URN =		{urn:nbn:de:0030-drops-115382},
  doi =		{10.4230/LIPIcs.ISAAC.2019.42},
  annote =	{Keywords: Discrete mathematics, Combinatorics, Reconstruction algorithm, Image reconstruction, Graph spectra, Grid graphs}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.47
Efficiently Realizing Interval Sequences

Authors: Amotz Bar-Noy, Keerti Choudhary, David Peleg, and Dror Rawitz

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract
We consider the problem of realizable interval-sequences. An interval sequence comprises of n integer intervals [a_i,b_i] such that 0 <= a_i <= b_i <= n-1, and is said to be graphic/realizable if there exists a graph with degree sequence, say, D=(d_1,...,d_n) satisfying the condition a_i <= d_i <= b_i, for each i in [1,n]. There is a characterisation (also implying an O(n) verifying algorithm) known for realizability of interval-sequences, which is a generalization of the Erdös-Gallai characterisation for graphic sequences. However, given any realizable interval-sequence, there is no known algorithm for computing a corresponding graphic certificate in o(n^2) time. In this paper, we provide an O(n log n) time algorithm for computing a graphic sequence for any realizable interval sequence. In addition, when the interval sequence is non-realizable, we show how to find a graphic sequence having minimum deviation with respect to the given interval sequence, in the same time. Finally, we consider variants of the problem such as computing the most regular graphic sequence, and computing a minimum extension of a length p non-graphic sequence to a graphic one.
Cite as

Amotz Bar-Noy, Keerti Choudhary, David Peleg, and Dror Rawitz. Efficiently Realizing Interval Sequences. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 47:1-47:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{barnoy_et_al:LIPIcs.ISAAC.2019.47,
  author =	{Bar-Noy, Amotz and Choudhary, Keerti and Peleg, David and Rawitz, Dror},
  title =	{{Efficiently Realizing Interval Sequences}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{47:1--47:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.47},
  URN =		{urn:nbn:de:0030-drops-115430},
  doi =		{10.4230/LIPIcs.ISAAC.2019.47},
  annote =	{Keywords: Graph realization, graphic sequence, interval sequence}
}
Document
DOI: 10.4230/LIPIcs.ESA.2017.55
Local Search Algorithms for Maximum Carpool Matching

Authors: Gilad Kutiel and Dror Rawitz

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract
The Maximum Carpool Matching problem is a star packing problem in directed graphs. Formally, given a directed graph G = (V, A), a capacity function c: V -> N, and a weight function w: A -> R^+, a carpool matching is a subset of arcs, M subseteq A, such that every v in V satisfies: (i) d^{in}_M(v) cdot d^{out}_M(v) = 0, (ii) d^{in}_M(v) <= c(v), and (iii) d^{out}_M(v) <= 1. A vertex v for which d^{out}_M(v) = 1 is a passenger, and a vertex for which d^{out}_M(v) = 0 is a driver who has d^{in}_M(v) passengers. In the Maximum Carpool Matching problem the goal is to find a carpool matching M of maximum total weight. The problem arises when designing an online carpool service, such as Zimride, which tries to connect between users based on a similarity function. The problem is known to be NP-hard, even in the unweighted and uncapacitated case. The Maximum Group Carpool Matching problem, is an extension of Maximum Carpool Matching where each vertex represents an unsplittable group of passengers. Formally, each vertex u in V has a size s(u) in N, and the constraint d^{in}_M(v) <= c(v) is replaced with sum_{u:(u,v) in M} s(u) <= c(v). We show that Maximum Carpool Matching can be formulated as an unconstrained submodular maximization problem, thus it admits a 1/2-approximation algorithm. We show that the same formulation does not work for Maximum Group Carpool Matching, nevertheless, we present a local search (1/2 - epsilon)-approximation algorithm for Maximum Group Carpool Matching. For the unweighted variant of both problems when the maximum possible capacity, c_{max}, is bounded by a constant, we provide a local search (1/2 + 1/{2c_{max}} - epsilon)-approximation algorithm. We also show that the problem is APX-hard, even if the maximum degree and c_{max} are at most 3.
Cite as

Gilad Kutiel and Dror Rawitz. Local Search Algorithms for Maximum Carpool Matching. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 55:1-55:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{kutiel_et_al:LIPIcs.ESA.2017.55,
  author =	{Kutiel, Gilad and Rawitz, Dror},
  title =	{{Local Search Algorithms for Maximum Carpool Matching}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{55:1--55:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.55},
  URN =		{urn:nbn:de:0030-drops-78210},
  doi =		{10.4230/LIPIcs.ESA.2017.55},
  annote =	{Keywords: approximation algorithms, local search, star packing, submodular maximization}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2015.11
Distributed Approximation of k-Service Assignment

Authors: Magnús M. Halldórsson, Sven Köhler, and Dror Rawitz

Published in: LIPIcs, Volume 46, 19th International Conference on Principles of Distributed Systems (OPODIS 2015)

Abstract
We consider the k-Service Assignment problem (k-SA), defined as follows. The input consists of a network that contains servers and clients, and an integer k. Each server has a finite capacity, and each client is associated with a demand and a profit. A feasible solution is an assignment of clients to neighboring servers such that (i) the total demand assigned to a server is at most its capacity, and (ii) a client is assigned either to k servers or to none. The profit of an assignment is the total profit of clients that are assigned to k servers, and the goal is to find a maximum profit assignment. In the r-restricted version of k-SA, no client requires more than an r-fraction of the capacity of any adjacent server. The k-SA problem is motivated by backup placement in networks and by resource allocation in 4G cellular networks. It can also be viewed as machine scheduling on related machines with assignment restrictions. We present a centralized polynomial time greedy (k+1-r)/(1-r)-approximation algorithm for r-restricted k-SA. We then show that a variant of this algorithm achieves an approximation ratio of k+1 using a resource augmentation factor of 1+r. We use the latter to present a (k+1)^2-approximation algorithm for k-SA. In the distributed setting, we present: (i) a (1+epsilon)*(k +1-r)/(1-r)-approximation algorithm for r-restricted k-SA, (ii) a (1+epsilon)(k+1)-approximation algorithm that uses a resource augmentation factor of 1+r for r-restricted k-SA, both for any constant epsilon>0, and (iii) an O{k^2}-approximation algorithm for k-SA (in expectation). The three distributed algorithms compute a solution with high probability and terminate in O(k^2 *log^3(n)) rounds.
Cite as

Magnús M. Halldórsson, Sven Köhler, and Dror Rawitz. Distributed Approximation of k-Service Assignment. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{halldorsson_et_al:LIPIcs.OPODIS.2015.11,
  author =	{Halld\'{o}rsson, Magn\'{u}s M. and K\"{o}hler, Sven and Rawitz, Dror},
  title =	{{Distributed Approximation of k-Service Assignment}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{11:1--11:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-98-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{46},
  editor =	{Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.11},
  URN =		{urn:nbn:de:0030-drops-66024},
  doi =		{10.4230/LIPIcs.OPODIS.2015.11},
  annote =	{Keywords: approximation algorithms, distributed algorithms, related machines}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.73
Online Budgeted Maximum Coverage

Authors: Dror Rawitz and Adi Rosén

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
We study the Online Budgeted Maximum Coverage (OBMC) problem. Subsets of a weighted ground set U arrive one by one, where each set has a cost. The online algorithm has to select a collection of sets, under the constraint that their cost is at most a given budget. Upon arrival of a set the algorithm must decide whether to accept or to reject the arriving set, and it may also drop previously accepted sets (preemption). Rejecting or dropping a set is irrevocable. The goal is to maximize the total weight of the elements covered by the sets in the chosen collection. We present a deterministic 4/(1-r)-competitive algorithm for OBMC, where r is the maximum ratio between the cost of a set and the total budget. Building on that algorithm, we then present a randomized O(1)-competitive algorithm for OBMC. On the other hand, we show that the competitive ratio of any deterministic online algorithm is Omega(1/(sqrt{1-r})). We also give a deterministic O(Delta)-competitive algorithm, where Delta is the maximum weight of a set (given that the minimum element weight is 1), and if the total weight of all elements, w(U), is known in advance, we show that a slight modification of that algorithm is O(min{Delta,sqrt{w(U)}})-competitive. A matching lower bound of Omega(min{Delta,sqrt{w(U)}}) is also given. Previous to the present work, only the unit cost version of OBMC was studied under the online setting, giving a 4-competitive algorithm [Saha, Getoor, 2009]. Finally, our results, including the lower bounds, apply to Removable Online Knapsack which is the preemptive version of the Online Knapsack problem.
Cite as

Dror Rawitz and Adi Rosén. Online Budgeted Maximum Coverage. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 73:1-73:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{rawitz_et_al:LIPIcs.ESA.2016.73,
  author =	{Rawitz, Dror and Ros\'{e}n, Adi},
  title =	{{Online Budgeted Maximum Coverage}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{73:1--73:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.73},
  URN =		{urn:nbn:de:0030-drops-64146},
  doi =		{10.4230/LIPIcs.ESA.2016.73},
  annote =	{Keywords: budgeted coverage, maximum coverage, online algorithms, competitive analysis, removable online knapsack}
}
Document
DOI: 10.4230/LIPIcs.STACS.2011.472
Online Scheduling with Interval Conflicts

Authors: Magnus M. Halldorsson, Boaz Patt-Shamir, and Dror Rawitz

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Abstract
In the problem of Scheduling with Interval Conflicts, there is a ground set of items indexed by integers, and the input is a collection of conflicts, each containing all the items whose index lies within some interval on the real line. Conflicts arrive in an online fashion. A scheduling algorithm must select, from each conflict, at most one survivor item, and the goal is to maximize the number (or weight) of items that survive all the conflicts they are involved in. We present a centralized deterministic online algorithm whose competitive ratio is O(log sigma), where sigma is the size of the largest conflict. For the distributed setting, we present another deterministic algorithm whose competitive ratio is 2 log sigma, in the special contiguous case, in which the item indices constitute a contiguous interval of integers. Our upper bounds are complemented by two lower bounds: one that shows that even in the contiguous case, all deterministic algorithms (centralized or distributed) have competitive ratio Omega(log sigma), and that in the non-contiguous case, no deterministic oblivious algorithm (i.e., a distributed algorithm that does not use communication) can have a bounded competitive ratio.
Cite as

Magnus M. Halldorsson, Boaz Patt-Shamir, and Dror Rawitz. Online Scheduling with Interval Conflicts. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 472-483, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{halldorsson_et_al:LIPIcs.STACS.2011.472,
  author =	{Halldorsson, Magnus M. and Patt-Shamir, Boaz and Rawitz, Dror},
  title =	{{Online Scheduling with Interval Conflicts}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{472--483},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.472},
  URN =		{urn:nbn:de:0030-drops-30363},
  doi =		{10.4230/LIPIcs.STACS.2011.472},
  annote =	{Keywords: online scheduling, online set packing, interval conflicts, competitive analysis, compound tasks, distributed algorithms}
}
Document
DOI: 10.4230/LIPIcs.STACS.2008.1331
Rent, Lease or Buy: Randomized Algorithms for Multislope Ski Rental

Authors: Zvi Lotker, Boaz Patt-Shamir, and Dror Rawitz

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

Abstract
In the Multislope Ski Rental problem, the user needs a certain resource for some unknown period of time. To use the resource, the user must subscribe to one of several options, each of which consists of a one-time setup cost (``buying price''), and cost proportional to the duration of the usage (``rental rate''). The larger the price, the smaller the rent. The actual usage time is determined by an adversary, and the goal of an algorithm is to minimize the cost by choosing the best option at any point in time. Multislope Ski Rental is a natural generalization of the classical Ski Rental problem (where the only options are pure rent and pure buy), which is one of the fundamental problems of online computation. The Multislope Ski Rental problem is an abstraction of many problems where online decisions cannot be modeled by just two options, e.g., power management in systems which can be shut down in parts. In this paper we study randomized algorithms for Multislope Ski Rental. Our results include the best possible online randomized strategy for any additive instance, where the cost of switching from one option to another is the difference in their buying prices; and an algorithm that produces an $e$-competitive randomized strategy for any (non-additive) instance.
Cite as

Zvi Lotker, Boaz Patt-Shamir, and Dror Rawitz. Rent, Lease or Buy: Randomized Algorithms for Multislope Ski Rental. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 503-514, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{lotker_et_al:LIPIcs.STACS.2008.1331,
  author =	{Lotker, Zvi and Patt-Shamir, Boaz and Rawitz, Dror},
  title =	{{Rent, Lease or Buy: Randomized Algorithms for Multislope Ski Rental}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{503--514},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1331},
  URN =		{urn:nbn:de:0030-drops-13313},
  doi =		{10.4230/LIPIcs.STACS.2008.1331},
  annote =	{Keywords: Competitive analysis, ski rental, randomized algorithms}
}
  • Refine by Author
  • 13 Rawitz, Dror
  • 8 Bar-Noy, Amotz
  • 8 Peleg, David
  • 3 Böhnlein, Toni
  • 3 Choudhary, Keerti
  • Show More...

  • Refine by Classification
  • 4 Mathematics of computing → Graph algorithms
  • 3 Mathematics of computing → Graph theory
  • 1 Mathematics of computing
  • 1 Mathematics of computing → Enumeration

  • Refine by Keyword
  • 3 Graph Realization
  • 3 Graph realization
  • 2 Bigraphic Sequences
  • 2 Bipartite Graphs
  • 2 Degree Sequences
  • Show More...

  • Refine by Type
  • 13 document

  • Refine by Publication Year
  • 3 2022
  • 2 2016
  • 2 2019
  • 2 2020
  • 1 2008
  • Show More...

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