Search Results

Documents authored by Iwama, Kazuo

Document
DOI: 10.4230/LIPIcs.ISAAC.2022.28
Improving the Bounds of the Online Dynamic Power Management Problem

Authors: Ya-Chun Liang, Kazuo Iwama, and Chung-Shou Liao

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
We investigate the power-down mechanism which decides when a machine transitions between states such that the total energy consumption, characterized by execution cost, idle cost and switching cost, is minimized. In contrast to most of the previous studies on the offline model, we focus on the online model in which a sequence of jobs with their release time, execution time and deadline, arrive in an online fashion. More precisely, we exploit a different switching on and off strategy and present an upper bound of 3, and further show a lower bound of 2.1, in a dual-machine model, introduced by Chen et al. in 2014 [STACS 2014: 226-238], both of which beat the currently best result.
Cite as

Ya-Chun Liang, Kazuo Iwama, and Chung-Shou Liao. Improving the Bounds of the Online Dynamic Power Management Problem. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 28:1-28:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{liang_et_al:LIPIcs.ISAAC.2022.28,
  author =	{Liang, Ya-Chun and Iwama, Kazuo and Liao, Chung-Shou},
  title =	{{Improving the Bounds of the Online Dynamic Power Management Problem}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{28:1--28:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.28},
  URN =		{urn:nbn:de:0030-drops-173138},
  doi =		{10.4230/LIPIcs.ISAAC.2022.28},
  annote =	{Keywords: Online algorithm, Energy scheduling, Dynamic power management}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.50
Tight Competitive Analyses of Online Car-Sharing Problems

Authors: Ya-Chun Liang, Kuan-Yun Lai, Ho-Lin Chen, and Kazuo Iwama

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

Abstract
The car-sharing problem, proposed by Luo, Erlebach and Xu in 2018, mainly focuses on an online model in which there are two locations: 0 and 1, and k total cars. Each request which specifies its pick-up time and pick-up location (among 0 and 1, and the other is the drop-off location) is released in each stage a fixed amount of time before its specified start (i.e. pick-up) time. The time between the booking (i.e. released) time and the start time is enough to move empty cars between 0 and 1 for relocation if they are not used in that stage. The model, called kS2L-F, assumes that requests in each stage arrive sequentially regardless of the same booking time and the decision (accept or reject) must be made immediately. The goal is to accept as many requests as possible. In spite of only two locations, the analysis does not seem easy and the (tight) competitive ratio (CR) is only known to be 2.0 for k = 2 and 1.5 for a restricted value of k, i.e., a multiple of three. In this paper, we remove all the holes of unknown CR’s; namely we prove that the CR is 2k/(k + ⌊k/3⌋) for all k ≥ 2. Furthermore, if the algorithm can delay its decision until all requests have come in each stage, the CR is improved to roughly 4/3. We can take this advantage even further, precisely we can achieve a CR of (2+R)/3 if the number of requests in each stage is at most Rk, 1 ≤ R ≤ 2, where we do not have to know the value of R in advance. Finally we demonstrate that randomization also helps to get (slightly) better CR’s.
Cite as

Ya-Chun Liang, Kuan-Yun Lai, Ho-Lin Chen, and Kazuo Iwama. Tight Competitive Analyses of Online Car-Sharing Problems. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 50:1-50:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{liang_et_al:LIPIcs.ISAAC.2021.50,
  author =	{Liang, Ya-Chun and Lai, Kuan-Yun and Chen, Ho-Lin and Iwama, Kazuo},
  title =	{{Tight Competitive Analyses of Online Car-Sharing Problems}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{50:1--50:14},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.50},
  URN =		{urn:nbn:de:0030-drops-154835},
  doi =		{10.4230/LIPIcs.ISAAC.2021.50},
  annote =	{Keywords: Car-sharing, Competitive analysis, On-line scheduling, Randomized algorithm}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2016.23
Total Stability in Stable Matching Games

Authors: Sushmita Gupta, Kazuo Iwama, and Shuichi Miyazaki

Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)

Abstract
The stable marriage problem (SMP) can be seen as a typical game, where each player wants to obtain the best possible partner by manipulating his/her preference list. Thus the set Q of preference lists submitted to the matching agency may differ from P, the set of true preference lists. In this paper, we study the stability of the stated lists in Q. If Q is not Nash equilibrium, i.e., if a player can obtain a strictly better partner (with respect to the preference order in P) by only changing his/her list, then in the view of standard game theory, Q is vulnerable. In the case of SMP, however, we need to consider another factor, namely that all valid matchings should not include any "blocking pairs" with respect to P. Thus, if the above manipulation of a player introduces blocking pairs, it would prevent this manipulation. Consequently, we say Q is totally stable if either Q is a Nash equilibrium or if any attempt at manipulation by a single player causes blocking pairs with respect to P. We study the complexity of testing the total stability of a stated strategy. It is known that this question is answered in polynomial time if the instance (P,Q) always satisfies P=Q. We extend this polynomially solvable class to the general one, where P and Q may be arbitrarily different.
Cite as

Sushmita Gupta, Kazuo Iwama, and Shuichi Miyazaki. Total Stability in Stable Matching Games. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 23:1-23:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{gupta_et_al:LIPIcs.SWAT.2016.23,
  author =	{Gupta, Sushmita and Iwama, Kazuo and Miyazaki, Shuichi},
  title =	{{Total Stability in Stable Matching Games}},
  booktitle =	{15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
  pages =	{23:1--23:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-011-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{53},
  editor =	{Pagh, Rasmus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.23},
  URN =		{urn:nbn:de:0030-drops-60450},
  doi =		{10.4230/LIPIcs.SWAT.2016.23},
  annote =	{Keywords: stable matching, Gale-Shapley algorithm, manipulation, stability, Nash equilibrium}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.361
A Tight Approximation Bound for the Stable Marriage Problem with Restricted Ties

Authors: Chien-Chung Huang, Kazuo Iwama, Shuichi Miyazaki, and Hiroki Yanagisawa

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

Abstract
The problem of finding a maximum cardinality stable matching in the presence of ties and unacceptable partners, called MAX SMTI, is a well-studied NP-hard problem. The MAX SMTI is NP-hard even for highly restricted instances where (i) ties appear only in women's preference lists and (ii) each tie appears at the end of each woman's preference list. The current best lower bounds on the approximation ratio for this variant are 1.1052 unless P=NP and 1.25 under the unique games conjecture, while the current best upper bound is 1.4616. In this paper, we improve the upper bound to 1.25, which matches the lower bound under the unique games conjecture. Note that this is the first special case of the MAX SMTI where the tight approximation bound is obtained. The improved ratio is achieved via a new analysis technique, which avoids the complicated case-by-case analysis used in earlier studies. As a by-product of our analysis, we show that the integrality gap of natural IP and LP formulations for this variant is 1.25. We also show that the unrestricted MAX SMTI cannot be approximated with less than 1.5 unless the approximation ratio of a certain special case of the minimum maximal matching problem can be improved.
Cite as

Chien-Chung Huang, Kazuo Iwama, Shuichi Miyazaki, and Hiroki Yanagisawa. A Tight Approximation Bound for the Stable Marriage Problem with Restricted Ties. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 361-380, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.APPROX-RANDOM.2015.361,
  author =	{Huang, Chien-Chung and Iwama, Kazuo and Miyazaki, Shuichi and Yanagisawa, Hiroki},
  title =	{{A Tight Approximation Bound for the Stable Marriage Problem with Restricted Ties}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{361--380},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.361},
  URN =		{urn:nbn:de:0030-drops-53123},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.361},
  annote =	{Keywords: stable marriage with ties and incomplete lists, approximation algorithm, integer program, linear program relaxation, integrality gap}
}
Document
DOI: 10.4230/LIPIcs.STACS.2014.409
Read-Once Branching Programs for Tree Evaluation Problems

Authors: Kazuo Iwama and Atsuki Nagao

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Abstract
Toward the ultimate goal of separating L and P, Cook, McKenzie, Wehr, Braverman and Santhanam introduced the tree evaluation problem (TEP). For fixed h, k>0, FT_h(k) is given as a complete, rooted binary tree of height h, in which each internal node is associated with a function from [k]^2 to [k], and each leaf node with a number in [k]. The value of an internal node v is defined naturally, i.e., if it has a function f and the values of its two child nodes are a and b, then the value of v is f(a,b). Our task is to compute the value of the root node by sequentially executing this function evaluation in a bottom-up fashion. The problem is obviously in P and if we could prove that any branching program solving FT_h(k) needs at least k^(r(h)) states for any unbounded function r, then this problem is not in L, thus achieving our goal. The above authors introduced a restriction called thrifty against the structure of BP’s (i,e., against the algorithm for solving the problem) and proved that any thrifty BP needs Omega(k^h) states. This paper proves a similar lower bound for read-once branching programs, which allows us to get rid of the restriction on the order of nodes read by the BP that is the nature of the thrifty restriction.
Cite as

Kazuo Iwama and Atsuki Nagao. Read-Once Branching Programs for Tree Evaluation Problems. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 409-420, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{iwama_et_al:LIPIcs.STACS.2014.409,
  author =	{Iwama, Kazuo and Nagao, Atsuki},
  title =	{{Read-Once Branching Programs for Tree Evaluation Problems}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{409--420},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.409},
  URN =		{urn:nbn:de:0030-drops-44756},
  doi =		{10.4230/LIPIcs.STACS.2014.409},
  annote =	{Keywords: Lower bounds, Branching Programs, Read-Once Branching Programs, Space Complexity, Combinatorics}
}
Document
DOI: 10.4230/DagSemProc.08431.1
08431 Abstracts Collection – Moderately Exponential Time Algorithms

Authors: Fedor V. Fomin, Kazuo Iwama, and Dieter Kratsch

Published in: Dagstuhl Seminar Proceedings, Volume 8431, Moderately Exponential Time Algorithms (2008)

Abstract
From $19/10/2008$ to $24/10/2008$, the Dagstuhl Seminar 08431 ``Moderately Exponential Time Algorithms '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Fedor V. Fomin, Kazuo Iwama, and Dieter Kratsch. 08431 Abstracts Collection – Moderately Exponential Time Algorithms. In Moderately Exponential Time Algorithms. Dagstuhl Seminar Proceedings, Volume 8431, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{fomin_et_al:DagSemProc.08431.1,
  author =	{Fomin, Fedor V. and Iwama, Kazuo and Kratsch, Dieter},
  title =	{{08431 Abstracts Collection – Moderately Exponential Time Algorithms}},
  booktitle =	{Moderately Exponential Time Algorithms},
  pages =	{1--22},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8431},
  editor =	{Fedor V. Fomin and Kazuo Iwama and Dieter Kratsch},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08431.1},
  URN =		{urn:nbn:de:0030-drops-18004},
  doi =		{10.4230/DagSemProc.08431.1},
  annote =	{Keywords: Algorithms, Exponential time algorithms, Graphs, SAT}
}
Document
DOI: 10.4230/DagSemProc.08431.2
08431 Executive Summary – Moderately Exponential Time Algorithms

Authors: Fedor V. Fomin, Kazuo Iwama, and Dieter Kratsch

Published in: Dagstuhl Seminar Proceedings, Volume 8431, Moderately Exponential Time Algorithms (2008)

Abstract
The Dagstuhl seminar on Moderately Exponential Time Algorithms took place from 19.10.08 to 24.10.08. The 54 participants came from 18 countries. There were 27 talks and 2 open problem sessions. Talks were complemented by intensive informal discussions, and many new research directions and open problems will result from these discussions. The warm and encouraging Dagstuhl atmosphere stimulated new research projects.
Cite as

Fedor V. Fomin, Kazuo Iwama, and Dieter Kratsch. 08431 Executive Summary – Moderately Exponential Time Algorithms. In Moderately Exponential Time Algorithms. Dagstuhl Seminar Proceedings, Volume 8431, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{fomin_et_al:DagSemProc.08431.2,
  author =	{Fomin, Fedor V. and Iwama, Kazuo and Kratsch, Dieter},
  title =	{{08431 Executive Summary – Moderately Exponential Time Algorithms}},
  booktitle =	{Moderately Exponential Time Algorithms},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8431},
  editor =	{Fedor V. Fomin and Kazuo Iwama and Dieter Kratsch},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08431.2},
  URN =		{urn:nbn:de:0030-drops-17976},
  doi =		{10.4230/DagSemProc.08431.2},
  annote =	{Keywords: Algorithms, NP-hard problems, Exact algorithms, Moderately Exponential Time Algorithms}
}
Document
DOI: 10.4230/DagSemProc.08431.3
08431 Open Problems – Moderately Exponential Time Algorithms

Authors: Fedor V. Fomin, Kazuo Iwama, Dieter Kratsch, Petteri Kaski, Mikko Koivisto, Lukasz Kowalik, Yoshio Okamoto, Johan van Rooij, and Ryan Williams

Published in: Dagstuhl Seminar Proceedings, Volume 8431, Moderately Exponential Time Algorithms (2008)

Abstract
Two problem sessions were part of the seminar on Moderately Exponential Time Algorithms. Some of the open problems presented at those sessions have been collected.
Cite as

Fedor V. Fomin, Kazuo Iwama, Dieter Kratsch, Petteri Kaski, Mikko Koivisto, Lukasz Kowalik, Yoshio Okamoto, Johan van Rooij, and Ryan Williams. 08431 Open Problems – Moderately Exponential Time Algorithms. In Moderately Exponential Time Algorithms. Dagstuhl Seminar Proceedings, Volume 8431, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{fomin_et_al:DagSemProc.08431.3,
  author =	{Fomin, Fedor V. and Iwama, Kazuo and Kratsch, Dieter and Kaski, Petteri and Koivisto, Mikko and Kowalik, Lukasz and Okamoto, Yoshio and van Rooij, Johan and Williams, Ryan},
  title =	{{08431 Open Problems – Moderately Exponential Time Algorithms}},
  booktitle =	{Moderately Exponential Time Algorithms},
  pages =	{1--8},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8431},
  editor =	{Fedor V. Fomin and Kazuo Iwama and Dieter Kratsch},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08431.3},
  URN =		{urn:nbn:de:0030-drops-17986},
  doi =		{10.4230/DagSemProc.08431.3},
  annote =	{Keywords: Algorithms, NP-hard problems, Moderately Exponential Time Algorithms}
}
Document
DOI: 10.4230/DagSemProc.06111.14
Quantum Network Coding

Authors: Masahito Hayashi, Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, and Shigeru Yamashita

Published in: Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)

Abstract
Since quantum information is continuous, its handling is sometimes surprisingly harder than the classical counterpart. A typical example is cloning; making a copy of digital information is straightforward but it is not possible exactly for quantum information. The question in this paper is whether or not {em quantum} network coding is possible. Its classical counterpart is another good example to show that digital information flow can be done much more efficiently than conventional (say, liquid) flow. Our answer to the question is similar to the case of cloning, namely, it is shown that quantum network coding is possible if approximation is allowed, by using a simple network model called Butterfly. In this network, there are two flow paths, $s_1$ to $t_1$ and $s_2$ to $t_2$, which shares a single bottleneck channel of capacity one. In the classical case, we can send two bits simultaneously, one for each path, in spite of the bottleneck. Our results for quantum network coding include: (i) We can send any quantum state $|psi_1 angle$ from $s_1$ to $t_1$ and $|psi_2 angle$ from $s_2$ to $t_2$ simultaneously with a fidelity strictly greater than $1/2$. (ii) If one of $|psi_1 angle$ and $|psi_2 angle$ is classical, then the fidelity can be improved to $2/3$. (iii) Similar improvement is also possible if $|psi_1 angle$ and $|psi_2 angle$ are restricted to only a finite number of (previously known) states. (iv) Several impossibility results including the general upper bound of the fidelity are also given.
Cite as

Masahito Hayashi, Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, and Shigeru Yamashita. Quantum Network Coding. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{hayashi_et_al:DagSemProc.06111.14,
  author =	{Hayashi, Masahito and Iwama, Kazuo and Nishimura, Harumichi and Raymond, Rudy and Yamashita, Shigeru},
  title =	{{Quantum Network Coding}},
  booktitle =	{Complexity of Boolean Functions},
  pages =	{1--17},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6111},
  editor =	{Matthias Krause and Pavel Pudl\'{a}k and R\"{u}diger Reischuk and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06111.14},
  URN =		{urn:nbn:de:0030-drops-6080},
  doi =		{10.4230/DagSemProc.06111.14},
  annote =	{Keywords: Network coding, quantum computation, quantum information}
}
Document
DOI: 10.4230/DagSemProc.05031.8
Average-Case Competitive Analyses for Ski-Rental Problems

Authors: Hiroshi Fujiwara and Kazuo Iwama

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

Abstract
Let $s$ be the ratio of the cost for purchasing skis over the cost for renting them. Then the famous result for the ski-rental problem shows that skiers should buy their skis after renting them $(s-1)$ times, which gives us an optimal competitive ratio of $2-\frac{1}{s}$. In practice, however, it appears that many skiers buy their skis before this optimal point of time and also many skiers keep renting them forever. In this paper we show that these behaviors of skiers are quite reasonable by using an {\em average-case competitive ratio}. For an exponential input distribution $f(t) = \lambda e^{-\lambda t}$, optimal strategies are (i) if $\frac{1}{\lambda} \leq s$, then skiers should rent their skis forever and (ii) otherwise should purchase them after renting approximately $s^2\lambda \;\;(
Cite as

Hiroshi Fujiwara and Kazuo Iwama. Average-Case Competitive Analyses for Ski-Rental Problems. 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{fujiwara_et_al:DagSemProc.05031.8,
  author =	{Fujiwara, Hiroshi and Iwama, Kazuo},
  title =	{{Average-Case Competitive Analyses for Ski-Rental Problems}},
  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.8},
  URN =		{urn:nbn:de:0030-drops-606},
  doi =		{10.4230/DagSemProc.05031.8},
  annote =	{Keywords: online algorithm , competitive analysis}
}
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