Search Results

Documents authored by Levin, Asaf

Document
DOI: 10.4230/LIPIcs.STACS.2022.28
Cardinality Constrained Scheduling in Online Models

Authors: Leah Epstein, Alexandra Lassota, Asaf Levin, Marten Maack, and Lars Rohwedder

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
Makespan minimization on parallel identical machines is a classical and intensively studied problem in scheduling, and a classic example for online algorithm analysis with Graham’s famous list scheduling algorithm dating back to the 1960s. In this problem, jobs arrive over a list and upon an arrival, the algorithm needs to assign the job to a machine. The goal is to minimize the makespan, that is, the maximum machine load. In this paper, we consider the variant with an additional cardinality constraint: The algorithm may assign at most k jobs to each machine where k is part of the input. While the offline (strongly NP-hard) variant of cardinality constrained scheduling is well understood and an EPTAS exists here, no non-trivial results are known for the online variant. We fill this gap by making a comprehensive study of various different online models. First, we show that there is a constant competitive algorithm for the problem and further, present a lower bound of 2 on the competitive ratio of any online algorithm. Motivated by the lower bound, we consider a semi-online variant where upon arrival of a job of size p, we are allowed to migrate jobs of total size at most a constant times p. This constant is called the migration factor of the algorithm. Algorithms with small migration factors are a common approach to bridge the performance of online algorithms and offline algorithms. One can obtain algorithms with a constant migration factor by rounding the size of each incoming job and then applying an ordinal algorithm to the resulting rounded instance. With this in mind, we also consider the framework of ordinal algorithms and characterize the competitive ratio that can be achieved using the aforementioned approaches. More specifically, we show that in both cases, one can get a competitive ratio that is strictly lower than 2, which is the bound from the standard online setting. On the other hand, we prove that no PTAS is possible.
Cite as

Leah Epstein, Alexandra Lassota, Asaf Levin, Marten Maack, and Lars Rohwedder. Cardinality Constrained Scheduling in Online Models. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 28:1-28:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{epstein_et_al:LIPIcs.STACS.2022.28,
  author =	{Epstein, Leah and Lassota, Alexandra and Levin, Asaf and Maack, Marten and Rohwedder, Lars},
  title =	{{Cardinality Constrained Scheduling in Online Models}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{28:1--28:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.28},
  URN =		{urn:nbn:de:0030-drops-158385},
  doi =		{10.4230/LIPIcs.STACS.2022.28},
  annote =	{Keywords: Cardinality Constrained Scheduling, Makespan Minimization, Online Algorithms, Lower Bounds, Pure Online, Migration, Ordinal Algorithms}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2021.8
Truly Asymptotic Lower Bounds for Online Vector Bin Packing

Authors: János Balogh, Ilan Reuven Cohen, Leah Epstein, and Asaf Levin

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

Abstract
In this work, we consider online d-dimensional vector bin packing. It is known that no algorithm can have a competitive ratio of o(d/log² d) in the absolute sense, although upper bounds for this problem have always been presented in the asymptotic sense. Since variants of bin packing are traditionally studied with respect to the asymptotic measure, and since the two measures are different, we focus on the asymptotic measure and prove new lower bounds of the asymptotic competitive ratio. The existing lower bounds prior to this work were known to be smaller than 3, even for very large d. Here, we significantly improved on the best known lower bounds of the asymptotic competitive ratio (and as a byproduct, on the absolute competitive ratio) for online vector packing of vectors with d ≥ 3 dimensions, for every dimension d. To obtain these results, we use several different constructions, one of which is an adaptive construction with a lower bound of Ω(√d). Our main result is that the lower bound of Ω(d/log² d) on the competitive ratio holds also in the asymptotic sense. This result holds also against randomized algorithms, and requires a careful adaptation of constructions for online coloring, rather than simple black-box reductions.
Cite as

János Balogh, Ilan Reuven Cohen, Leah Epstein, and Asaf Levin. Truly Asymptotic Lower Bounds for Online Vector Bin Packing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 8:1-8:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{balogh_et_al:LIPIcs.APPROX/RANDOM.2021.8,
  author =	{Balogh, J\'{a}nos and Cohen, Ilan Reuven and Epstein, Leah and Levin, Asaf},
  title =	{{Truly Asymptotic Lower Bounds for Online Vector Bin Packing}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{8:1--8:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.8},
  URN =		{urn:nbn:de:0030-drops-147013},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.8},
  annote =	{Keywords: Bin packing, online algorithms, approximation algorithms, vector packing}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.18
Online Bin Covering with Limited Migration

Authors: Sebastian Berndt, Leah Epstein, Klaus Jansen, Asaf Levin, Marten Maack, and Lars Rohwedder

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
Semi-online models where decisions may be revoked in a limited way have been studied extensively in the last years. This is motivated by the fact that the pure online model is often too restrictive to model real-world applications, where some changes might be allowed. A well-studied measure of the amount of decisions that can be revoked is the migration factor beta: When an object o of size s(o) arrives, the decisions for objects of total size at most beta * s(o) may be revoked. Usually beta should be a constant. This means that a small object only leads to small changes. This measure has been successfully investigated for different, classical problems such as bin packing or makespan minimization. The dual of makespan minimization - the Santa Claus or machine covering problem - has also been studied, whereas the dual of bin packing - the bin covering problem - has not been looked at from such a perspective. In this work, we extensively study the bin covering problem with migration in different scenarios. We develop algorithms both for the static case - where only insertions are allowed - and for the dynamic case, where items may also depart. We also develop lower bounds for these scenarios both for amortized migration and for worst-case migration showing that our algorithms have nearly optimal migration factor and asymptotic competitive ratio (up to an arbitrary small epsilon). We therefore resolve the competitiveness of the bin covering problem with migration.
Cite as

Sebastian Berndt, Leah Epstein, Klaus Jansen, Asaf Levin, Marten Maack, and Lars Rohwedder. Online Bin Covering with Limited Migration. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 18:1-18:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{berndt_et_al:LIPIcs.ESA.2019.18,
  author =	{Berndt, Sebastian and Epstein, Leah and Jansen, Klaus and Levin, Asaf and Maack, Marten and Rohwedder, Lars},
  title =	{{Online Bin Covering with Limited Migration}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{18:1--18:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola 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.2019.18},
  URN =		{urn:nbn:de:0030-drops-111391},
  doi =		{10.4230/LIPIcs.ESA.2019.18},
  annote =	{Keywords: online algorithms, dynamic algorithms, competitive ratio, bin covering, migration factor}
}
Document
DOI: 10.4230/LIPIcs.ESA.2018.5
A New and Improved Algorithm for Online Bin Packing

Authors: János Balogh, József Békési, György Dósa, Leah Epstein, and Asaf Levin

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

Abstract
We revisit the classic online bin packing problem studied in the half-century. In this problem, items of positive sizes no larger than 1 are presented one by one to be packed into subsets called bins of total sizes no larger than 1, such that every item is assigned to a bin before the next item is presented. We use online partitioning of items into classes based on sizes, as in previous work, but we also apply a new method where items of one class can be packed into more than two types of bins, where a bin type is defined according to the number of such items grouped together. Additionally, we allow the smallest class of items to be packed in multiple kinds of bins, and not only into their own bins. We combine this with the approach of packing of sufficiently big items according to their exact sizes. Finally, we simplify the analysis of such algorithms, allowing the analysis to be based on the most standard weight functions. This simplified analysis allows us to study the algorithm which we defined based on all these ideas. This leads us to the design and analysis of the first algorithm of asymptotic competitive ratio strictly below 1.58, specifically, we break this barrier by providing an algorithm AH (Advanced Harmonic) whose asymptotic competitive ratio does not exceed 1.57829. Our main contribution is the introduction of the simple analysis based on weight function to analyze the state of the art online algorithms for the classic online bin packing problem. The previously used analytic tool named weight system was too complicated for the community in this area to adjust it for other problems and other algorithmic tools that are needed in order to improve the current best algorithms. We show that the weight system based analysis is not needed for the analysis of the current algorithms for the classic online bin packing problem. The importance of a simple analysis is demonstrated by analyzing several new features together with all existing techniques, and by proving a better competitive ratio than the previously best one.
Cite as

János Balogh, József Békési, György Dósa, Leah Epstein, and Asaf Levin. A New and Improved Algorithm for Online Bin Packing. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{balogh_et_al:LIPIcs.ESA.2018.5,
  author =	{Balogh, J\'{a}nos and B\'{e}k\'{e}si, J\'{o}zsef and D\'{o}sa, Gy\"{o}rgy and Epstein, Leah and Levin, Asaf},
  title =	{{A New and Improved Algorithm for Online Bin Packing}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{5:1--5: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.5},
  URN =		{urn:nbn:de:0030-drops-94686},
  doi =		{10.4230/LIPIcs.ESA.2018.5},
  annote =	{Keywords: Bin packing, online algorithms, competitive analysis}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.85
A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs

Authors: Martin Koutecký, Asaf Levin, and Shmuel Onn

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
The theory of n-fold integer programming has been recently emerging as an important tool in parameterized complexity. The input to an n-fold integer program (IP) consists of parameter A, dimension n, and numerical data of binary encoding length L. It was known for some time that such programs can be solved in polynomial time using O(n^{g(A)}L) arithmetic operations where g is an exponential function of the parameter. In 2013 it was shown that it can be solved in fixed-parameter tractable time using O(f(A)n^3L) arithmetic operations for a single-exponential function f. This, and a faster algorithm for a special case of combinatorial n-fold IP, have led to several very recent breakthroughs in the parameterized complexity of scheduling, stringology, and computational social choice. In 2015 it was shown that it can be solved in strongly polynomial time using O(n^{g(A)}) arithmetic operations. Here we establish a result which subsumes all three of the above results by showing that n-fold IP can be solved in strongly polynomial fixed-parameter tractable time using O(f(A)n^6 log n) arithmetic operations. In fact, our results are much more general, briefly outlined as follows. - There is a strongly polynomial algorithm for integer linear programming (ILP) whenever a so-called Graver-best oracle is realizable for it. - Graver-best oracles for the large classes of multi-stage stochastic and tree-fold ILPs can be realized in fixed-parameter tractable time. Together with the previous oracle algorithm, this newly shows two large classes of ILP to be strongly polynomial; in contrast, only few classes of ILP were previously known to be strongly polynomial. - We show that ILP is fixed-parameter tractable parameterized by the largest coefficient |A |_infty and the primal or dual treedepth of A, and that this parameterization cannot be relaxed, signifying substantial progress in understanding the parameterized complexity of ILP.
Cite as

Martin Koutecký, Asaf Levin, and Shmuel Onn. A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 85:1-85:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{koutecky_et_al:LIPIcs.ICALP.2018.85,
  author =	{Kouteck\'{y}, Martin and Levin, Asaf and Onn, Shmuel},
  title =	{{A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{85:1--85:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.85},
  URN =		{urn:nbn:de:0030-drops-90898},
  doi =		{10.4230/LIPIcs.ICALP.2018.85},
  annote =	{Keywords: integer programming, parameterized complexity, Graver basis, n-fold integer programming}
}
Document
DOI: 10.4230/LIPIcs.ESA.2017.10
Online Bin Packing with Cardinality Constraints Resolved

Authors: Janos Balogh, Jozsef Bekesi, Gyorgy Dosa, Leah Epstein, and Asaf Levin

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

Abstract
Cardinality constrained bin packing or bin packing with cardinality constraints is a basic bin packing problem. In the online version with the parameter k >= 2, items having sizes in (0,1] associated with them are presented one by one to be packed into unit capacity bins, such that the capacities of bins are not exceeded, and no bin receives more than k items. We resolve the online problem in the sense that we prove a lower bound of 2 on the overall asymptotic competitive ratio. This closes the long standing open problem of finding the value of the best possible overall asymptotic competitive ratio, since an algorithm of an absolute competitive ratio 2 for any fixed value of k is known. Additionally, we significantly improve the known lower bounds on the asymptotic competitive ratio for every specific value of k. The novelty of our constructions is based on full adaptivity that creates large gaps between item sizes. Thus, our lower bound inputs do not follow the common practice for online bin packing problems of having a known in advance input consisting of batches for which the algorithm needs to be competitive on every prefix of the input. Last, we show a lower bound strictly larger than 2 on the asymptotic competitive ratio of the online 2-dimensional vector packing problem, and thus provide for the first time a lower bound larger than 2 on the asymptotic competitive ratio for the vector packing problem in any fixed dimension.
Cite as

Janos Balogh, Jozsef Bekesi, Gyorgy Dosa, Leah Epstein, and Asaf Levin. Online Bin Packing with Cardinality Constraints Resolved. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{balogh_et_al:LIPIcs.ESA.2017.10,
  author =	{Balogh, Janos and Bekesi, Jozsef and Dosa, Gyorgy and Epstein, Leah and Levin, Asaf},
  title =	{{Online Bin Packing with Cardinality Constraints Resolved}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{10:1--10: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.10},
  URN =		{urn:nbn:de:0030-drops-78514},
  doi =		{10.4230/LIPIcs.ESA.2017.10},
  annote =	{Keywords: Online algorithms, bin packing, cardinality constraints, lower bounds}
}
Document
DOI: 10.4230/LIPIcs.STACS.2013.389
Improved Bounds for Online Preemptive Matching

Authors: Leah Epstein, Asaf Levin, Danny Segev, and Oren Weimann

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Abstract
When designing a preemptive online algorithm for the maximum matching problem, we wish to maintain a valid matching M while edges of the underlying graph are presented one after the other. When presented with an edge e, the algorithm should decide whether to augment the matching M by adding e (in which case e may be removed later on) or to keep M in its current form without adding e (in which case e is lost for good). The objective is to eventually hold a matching M with maximum weight. The main contribution of this paper is to establish new lower and upper bounds on the competitive ratio achievable by preemptive online algorithms: - We provide a lower bound of 1 + ln 2 \approx 1.693 on the competitive ratio of any randomized algorithm for the maximum cardinality matching problem, thus improving on the currently best known bound of e / (e-1) \approx 1.581 due to Karp, Vazirani, and Vazirani [STOC'90]. - We devise a randomized algorithm that achieves an expected competitive ratio of 5.356 for maximum weight matching. This finding demonstrates the power of randomization in this context, showing how to beat the tight bound of 3 + 2\sqrt{2} \approx 5.828 for deterministic algorithms, obtained by combining the 5.828 upper bound of McGregor [APPROX'05] and the recent 5.828 lower bound of Varadaraja [ICALP'11].
Cite as

Leah Epstein, Asaf Levin, Danny Segev, and Oren Weimann. Improved Bounds for Online Preemptive Matching. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 389-399, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{epstein_et_al:LIPIcs.STACS.2013.389,
  author =	{Epstein, Leah and Levin, Asaf and Segev, Danny and Weimann, Oren},
  title =	{{Improved Bounds for Online Preemptive Matching}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{389--399},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.389},
  URN =		{urn:nbn:de:0030-drops-39501},
  doi =		{10.4230/LIPIcs.STACS.2013.389},
  annote =	{Keywords: Online algorithms, matching, lower bound}
}
Document
DOI: 10.4230/LIPIcs.STACS.2010.2476
Improved Approximation Guarantees for Weighted Matching in the Semi-Streaming Model

Authors: Leah Epstein, Asaf Levin, Julián Mestre, and Danny Segev

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
We study the maximum weight matching problem in the semi-streaming model, and improve on the currently best one-pass algorithm due to Zelke (Proc.\ STACS~'08, pages 669--680) by devising a deterministic approach whose performance guarantee is $4.91 + \eps$. In addition, we study {\em preemptive} online algorithms, a sub-class of one-pass algorithms where we are only allowed to maintain a feasible matching in memory at any point in time. All known results prior to Zelke's belong to this sub-class. We provide a lower bound of $4.967$ on the competitive ratio of any such deterministic algorithm, and hence show that future improvements will have to store in memory a set of edges which is not necessarily a feasible matching. We conclude by presenting an empirical study, conducted in order to compare the practical performance of our approach to that of previously suggested algorithms.
Cite as

Leah Epstein, Asaf Levin, Julián Mestre, and Danny Segev. Improved Approximation Guarantees for Weighted Matching in the Semi-Streaming Model. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 347-358, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{epstein_et_al:LIPIcs.STACS.2010.2476,
  author =	{Epstein, Leah and Levin, Asaf and Mestre, Juli\'{a}n and Segev, Danny},
  title =	{{Improved Approximation Guarantees for Weighted Matching in the Semi-Streaming Model}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{347--358},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2476},
  URN =		{urn:nbn:de:0030-drops-24766},
  doi =		{10.4230/LIPIcs.STACS.2010.2476},
  annote =	{Keywords: Approximation guarantees, semi-streaming model, one-pass algorithm}
}
Document
DOI: 10.4230/DagSemProc.07261.4
Approximating min-max k-clustering

Authors: Asaf Levin

Published in: Dagstuhl Seminar Proceedings, Volume 7261, Fair Division (2007)

Abstract
We consider the problems of set partitioning into $k$ clusters with minimum of the maximum cost of a cluster. The cost function is given by an oracle, and we assume that it satisfies some natural structural constraints. That is, we assume that the cost function is monotone, the cost of a singleton is zero, and we assume that for all $S cap S' eq emptyset$ the following holds $c(S) + c(S') geq c(S cup S')$. For this problem we present a $(2k-1)$-approximation algorithm for $kgeq 3$, a 2-approximation algorithm for $k=2$, and we also show a lower bound of $k$ on the performance guarantee of any polynomial-time algorithm. We then consider special cases of this problem arising in vehicle routing problems, and present improved results.
Cite as

Asaf Levin. Approximating min-max k-clustering. In Fair Division. Dagstuhl Seminar Proceedings, Volume 7261, pp. 1-5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{levin:DagSemProc.07261.4,
  author =	{Levin, Asaf},
  title =	{{Approximating min-max k-clustering}},
  booktitle =	{Fair Division},
  pages =	{1--5},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7261},
  editor =	{Steven Brams and Kirk Pruhs and Gerhard Woeginger},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07261.4},
  URN =		{urn:nbn:de:0030-drops-12282},
  doi =		{10.4230/DagSemProc.07261.4},
  annote =	{Keywords: Approximation algorithms}
}
Document
DOI: 10.4230/DagSemProc.05031.30
Tracking mobile users

Authors: Leah Epstein and Asaf Levin

Published in: Dagstuhl Seminar Proceedings, Volume 5031, Algorithms for Optimization with Incomplete Information (2005)

Abstract
Cellular telephony systems, where locations of a mobile users may be unknown at some times, are becoming more common. Mobile users are roaming in a zone. A user reports its location only if it leaves the zone entirely. We consider cellular zones with n cells and m mobile users roaming among the cells. The location of the users is uncertain and is given by m probability distribution vectors. The Conference Call Search problem (CCS) deals with tracking a set of mobile users, in order to establish a call between all of them. The search is performed in a limited number of rounds, and the goal is to minimize the expected search cost. In the "unit cost model", a single query for a cell outputs a list of users located in that cell. The "bounded bandwidth" model allows a query for a single user per cell in each round. We discuss three types of protocols; oblivious, semi-adaptive and adaptive search protocols. An oblivious search protocol decides on all requests in advance, and stops only when all users are found. A semi-adaptive search protocol decides on all the requests in advance, but it stops searching for a user once it is found. An adaptive search protocol stops searching for a user once it has been found (and its search strategy may depend on the subsets of users that were found in each previous round). We establish the differences between the distinct protocol types and answer some open questions which were posed in previous work on the subject.
Cite as

Leah Epstein and Asaf Levin. Tracking mobile users. In Algorithms for Optimization with Incomplete Information. Dagstuhl Seminar Proceedings, Volume 5031, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{epstein_et_al:DagSemProc.05031.30,
  author =	{Epstein, Leah and Levin, Asaf},
  title =	{{Tracking mobile users}},
  booktitle =	{Algorithms for Optimization with Incomplete Information},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5031},
  editor =	{Susanne Albers and Rolf H. M\"{o}hring and Georg Ch. Pflug and R\"{u}diger Schultz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05031.30},
  URN =		{urn:nbn:de:0030-drops-580},
  doi =		{10.4230/DagSemProc.05031.30},
  annote =	{Keywords: mobile users , PTAS}
}
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