6 Search Results for "Jez, Lukasz"

Document
DOI: 10.4230/LIPIcs.ISAAC.2019.14
Slaying Hydrae: Improved Bounds for Generalized k-Server in Uniform Metrics

Authors: Marcin Bienkowski, Łukasz Jeż, and Paweł Schmidt

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

Abstract
The generalized k-server problem is an extension of the weighted k-server problem, which in turn extends the classic k-server problem. In the generalized k-server problem, each of k servers s_1, ..., s_k remains in its own metric space M_i. A request is a tuple (r_1,...,r_k), where r_i in M_i, and to service it, an algorithm needs to move at least one server s_i to the point r_i. The objective is to minimize the total distance traveled by all servers. In this paper, we focus on the generalized k-server problem for the case where all M_i are uniform metrics. We show an O(k^2 * log k)-competitive randomized algorithm improving over a recent result by Bansal et al. [SODA 2018], who gave an O(k^3 * log k)-competitive algorithm. To this end, we define an abstract online problem, called Hydra game, and we show that a randomized solution of low cost to this game implies a randomized algorithm to the generalized k-server problem with low competitive ratio. We also show that no randomized algorithm can achieve competitive ratio lower than Omega(k), thus improving the lower bound of Omega(k / log^2 k) by Bansal et al.
Cite as

Marcin Bienkowski, Łukasz Jeż, and Paweł Schmidt. Slaying Hydrae: Improved Bounds for Generalized k-Server in Uniform Metrics. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bienkowski_et_al:LIPIcs.ISAAC.2019.14,
  author =	{Bienkowski, Marcin and Je\.{z}, {\L}ukasz and Schmidt, Pawe{\l}},
  title =	{{Slaying Hydrae: Improved Bounds for Generalized k-Server in Uniform Metrics}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{14:1--14:14},
  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.14},
  URN =		{urn:nbn:de:0030-drops-115104},
  doi =		{10.4230/LIPIcs.ISAAC.2019.14},
  annote =	{Keywords: k-server, generalized k-server, competitive analysis}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.10
Dynamic Pricing of Servers on Trees

Authors: Ilan Reuven Cohen, Alon Eden, Amos Fiat, and Łukasz Jeż

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

Abstract
In this paper we consider the k-server problem where events are generated by selfish agents, known as the selfish k-server problem. In this setting, there is a set of k servers located in some metric space. Selfish agents arrive in an online fashion, each has a request located on some point in the metric space, and seeks to serve his request with the server of minimum distance to the request. If agents choose to serve their request with the nearest server, this mimics the greedy algorithm which has an unbounded competitive ratio. We propose an algorithm that associates a surcharge with each server independently of the agent to arrive (and therefore, yields a truthful online mechanism). An agent chooses to serve his request with the server that minimizes the distance to the request plus the associated surcharge to the server. This paper extends [Ilan Reuven Cohen et al., 2015], which gave an optimal k-competitive dynamic pricing scheme for the selfish k-server problem on the line. We give a k-competitive dynamic pricing algorithm for the selfish k-server problem on tree metric spaces, which matches the optimal online (non truthful) algorithm. We show that an alpha-competitive dynamic pricing scheme exists on the tree if and only if there exists alpha-competitive online algorithm on the tree that is lazy and monotone. Given this characterization, the main technical difficulty is coming up with such an online algorithm.
Cite as

Ilan Reuven Cohen, Alon Eden, Amos Fiat, and Łukasz Jeż. Dynamic Pricing of Servers on Trees. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 10:1-10:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.APPROX-RANDOM.2019.10,
  author =	{Cohen, Ilan Reuven and Eden, Alon and Fiat, Amos and Je\.{z}, {\L}ukasz},
  title =	{{Dynamic Pricing of Servers on Trees}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{10:1--10:22},
  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.10},
  URN =		{urn:nbn:de:0030-drops-112252},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.10},
  annote =	{Keywords: Online algorithms, Online mechanisms, k-server problem, Online pricing}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.8
Better Bounds for Online Line Chasing

Authors: Marcin Bienkowski, Jarosław Byrka, Marek Chrobak, Christian Coester, Łukasz Jeż, and Elias Koutsoupias

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract
We study online competitive algorithms for the line chasing problem in Euclidean spaces R^d, where the input consists of an initial point P_0 and a sequence of lines X_1, X_2, ..., X_m, revealed one at a time. At each step t, when the line X_t is revealed, the algorithm must determine a point P_t in X_t. An online algorithm is called c-competitive if for any input sequence the path P_0, P_1 , ..., P_m it computes has length at most c times the optimum path. The line chasing problem is a variant of a more general convex body chasing problem, where the sets X_t are arbitrary convex sets. To date, the best competitive ratio for the line chasing problem was 28.1, even in the plane. We improve this bound by providing a simple 3-competitive algorithm for any dimension d. We complement this bound by a matching lower bound for algorithms that are memoryless in the sense of our algorithm, and a lower bound of 1.5358 for arbitrary algorithms. The latter bound also improves upon the previous lower bound of sqrt{2}~=1.412 for convex body chasing in 2 dimensions.
Cite as

Marcin Bienkowski, Jarosław Byrka, Marek Chrobak, Christian Coester, Łukasz Jeż, and Elias Koutsoupias. Better Bounds for Online Line Chasing. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 8:1-8:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bienkowski_et_al:LIPIcs.MFCS.2019.8,
  author =	{Bienkowski, Marcin and Byrka, Jaros{\l}aw and Chrobak, Marek and Coester, Christian and Je\.{z}, {\L}ukasz and Koutsoupias, Elias},
  title =	{{Better Bounds for Online Line Chasing}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{8:1--8:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.8},
  URN =		{urn:nbn:de:0030-drops-109521},
  doi =		{10.4230/LIPIcs.MFCS.2019.8},
  annote =	{Keywords: convex body chasing, line chasing, competitive analysis}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2016.21
Online Packet Scheduling with Bounded Delay and Lookahead

Authors: Martin Böhm, Marek Chrobak, Lukasz Jez, Fei Li, Jirí Sgall, and Pavel Veselý

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

Abstract
We study the online bounded-delay packet scheduling problem (PacketScheduling), where packets of unit size arrive at a router over time and need to be transmitted over a network link. Each packet has two attributes: a non-negative weight and a deadline for its transmission. The objective is to maximize the total weight of the transmitted packets. This problem has been well studied in the literature, yet its optimal competitive ratio remains unknown: the best upper bound is 1.828 [Englert and Westermann, SODA 2007], still quite far from the best lower bound of phi approx 1.618 [Hajek, CISS 2001; Andelman et al, SODA 2003; Chin and Fung, Algorithmica, 2003]. In the variant of PacketScheduling with s-bounded instances, each packet can be scheduled in at most s consecutive slots, starting at its release time. The lower bound of phi applies even to the special case of 2-bounded instances, and a phi-competitive algorithm for 3-bounded instances was given in [Chin et al, JDA, 2006]. Improving that result, and addressing a question posed by Goldwasser [SIGACT News, 2010], we present a phi-competitive algorithm for 4-bounded instances. We also study a variant of PacketScheduling where an online algorithm has the additional power of 1-lookahead, knowing at time t which packets will arrive at time t+1. For PacketScheduling with 1-lookahead restricted to 2-bounded instances, we present an online algorithm with competitive ratio frac{1}{2}(sqrt{13} - 1) approx 1.303 and we prove a nearly tight lower bound of frac{1}{4}(1 + sqrt{17}) approx 1.281.
Cite as

Martin Böhm, Marek Chrobak, Lukasz Jez, Fei Li, Jirí Sgall, and Pavel Veselý. Online Packet Scheduling with Bounded Delay and Lookahead. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 21:1-21:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bohm_et_al:LIPIcs.ISAAC.2016.21,
  author =	{B\"{o}hm, Martin and Chrobak, Marek and Jez, Lukasz and Li, Fei and Sgall, Jir{\'\i} and Vesel\'{y}, Pavel},
  title =	{{Online Packet Scheduling with Bounded Delay and Lookahead}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{21:1--21: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.21},
  URN =		{urn:nbn:de:0030-drops-67901},
  doi =		{10.4230/LIPIcs.ISAAC.2016.21},
  annote =	{Keywords: buffer management, online scheduling, online algorithm, lookahead}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.12
Online Algorithms for Multi-Level Aggregation

Authors: Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukas Folwarczny, Lukasz Jez, Jiri Sgall, Nguyen Kim Thang, and Pavel Vesely

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

Abstract
In the Multi-Level Aggregation Problem (MLAP), requests arrive at the nodes of an edge-weighted tree T, and have to be served eventually. A service is defined as a subtree X of T that contains its root. This subtree X serves all requests that are pending in the nodes of X, and the cost of this service is equal to the total weight of X. Each request also incurs waiting cost between its arrival and service times. The objective is to minimize the total waiting cost of all requests plus the total cost of all service subtrees. MLAP is a generalization of some well-studied optimization problems; for example, for trees of depth 1, MLAP is equivalent to the TCP Acknowledgment Problem, while for trees of depth 2, it is equivalent to the Joint Replenishment Problem. Aggregation problem for trees of arbitrary depth arise in multicasting, sensor networks, communication in organization hierarchies, and in supply-chain management. The instances of MLAP associated with these applications are naturally online, in the sense that aggregation decisions need to be made without information about future requests. Constant-competitive online algorithms are known for MLAP with one or two levels. However, it has been open whether there exist constant competitive online algorithms for trees of depth more than 2. Addressing this open problem, we give the first constant competitive online algorithm for networks of arbitrary (fixed) number of levels. The competitive ratio is O(D^4*2^D), where D is the depth of T. The algorithm works for arbitrary waiting cost functions, including the variant with deadlines. We include several additional results in the paper. We show that a standard lower-bound technique for MLAP, based on so-called Single-Phase instances, cannot give super-constant lower bounds (as a function of the tree depth). This result is established by giving an online algorithm with optimal competitive ratio 4 for such instances on arbitrary trees. We also study the MLAP variant when the tree is a path, for which we give a lower bound of 4 on the competitive ratio, improving the lower bound known for general MLAP. We complement this with a matching upper bound for the deadline setting.
Cite as

Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukas Folwarczny, Lukasz Jez, Jiri Sgall, Nguyen Kim Thang, and Pavel Vesely. Online Algorithms for Multi-Level Aggregation. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bienkowski_et_al:LIPIcs.ESA.2016.12,
  author =	{Bienkowski, Marcin and B\"{o}hm, Martin and Byrka, Jaroslaw and Chrobak, Marek and D\"{u}rr, Christoph and Folwarczny, Lukas and Jez, Lukasz and Sgall, Jiri and Kim Thang, Nguyen and Vesely, Pavel},
  title =	{{Online Algorithms for Multi-Level Aggregation}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{12:1--12: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.12},
  URN =		{urn:nbn:de:0030-drops-63637},
  doi =		{10.4230/LIPIcs.ESA.2016.12},
  annote =	{Keywords: algorithmic aspects of networks, online algorithms, scheduling and resource allocation}
}
Document
DOI: 10.4230/LIPIcs.STACS.2010.2479
Randomized Algorithm for Agreeable Deadlines Packet Scheduling

Authors: Lukasz Jez

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

Abstract
In 2005 Li~et~al. gave a \(\phi\)-competitive deterministic online algorithm for scheduling of packets with agreeable deadlines~\cite{DBLP:conf/soda/LiSS05} with a very interesting analysis. This is known to be optimal due to a lower bound by Hajek~\cite{Hajek-det-lb}. We claim that the algorithm by Li~et~al. can be slightly simplified, while retaining its competitive ratio. Then we introduce randomness to the modified algorithm and argue that the competitive ratio against oblivious adversary is at most (\frac{4}{3}\). Note that this still leaves a gap between the best known lower bound of \(\frac{5}{4}\) by Chin~et~al.~\cite{DBLP:journals/algorithmica/ChinF03} for randomized algorithms against oblivious adversary.
Cite as

Lukasz Jez. Randomized Algorithm for Agreeable Deadlines Packet Scheduling. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 489-500, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{jez:LIPIcs.STACS.2010.2479,
  author =	{Jez, Lukasz},
  title =	{{Randomized Algorithm for Agreeable Deadlines Packet Scheduling}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{489--500},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2479},
  URN =		{urn:nbn:de:0030-drops-24795},
  doi =		{10.4230/LIPIcs.STACS.2010.2479},
  annote =	{Keywords: Online algorithms, scheduling, buffer management}
}
  • Refine by Author
  • 3 Bienkowski, Marcin
  • 3 Chrobak, Marek
  • 3 Jez, Lukasz
  • 3 Jeż, Łukasz
  • 2 Böhm, Martin
  • Show More...

  • Refine by Classification
  • 3 Theory of computation → Online algorithms
  • 1 Theory of computation → Algorithmic mechanism design

  • Refine by Keyword
  • 2 Online algorithms
  • 2 buffer management
  • 2 competitive analysis
  • 1 Online mechanisms
  • 1 Online pricing
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 3 2019
  • 2 2016
  • 1 2010

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