Competitive Analysis for the Flat-Rate Problem

Hiroshi FUJIWARA; Atsushi MATSUDA; Toshihiro FUJITO

doi:10.1587/transinf.2015FCP0005

Competitive Analysis for the Flat-Rate Problem

Hiroshi FUJIWARA, Atsushi MATSUDA, Toshihiro FUJITO

Full Text Views

0

Share
Cite this

Summary :

We consider a problem of the choice of price plans offered by a telecommunications company: a “pay-as-you-go” plan and a “flat-rate” plan. This problem is formulated as an online optimization problem extending the ski-rental problem, and analyzed using the competitive ratio. We give a lemma for easily calculating the competitive ratio. Based on the lemma, we derive a family of optimal strategies for a realistic class of instances.

Publication: IEICE TRANSACTIONS on Information Vol.E99-D No.3 pp.559-566

Publication Date: 2016/03/01

Publicized: 2015/12/16

Online ISSN: 1745-1361

DOI: 10.1587/transinf.2015FCP0005

Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science---Developments of the Theory of Algorithms and Computation---)

Category

Authors

Hiroshi FUJIWARA
  Shinshu University
Atsushi MATSUDA
  System Energy Co., Ltd.
Toshihiro FUJITO
  Toyohashi University of Technology

Keyword

online algorithm, competitive analysis, online optimization, ski-rental problems

Cite this

Copy

Hiroshi FUJIWARA, Atsushi MATSUDA, Toshihiro FUJITO, "Competitive Analysis for the Flat-Rate Problem" in IEICE TRANSACTIONS on Information, vol. E99-D, no. 3, pp. 559-566, March 2016, doi: 10.1587/transinf.2015FCP0005.
Abstract: We consider a problem of the choice of price plans offered by a telecommunications company: a “pay-as-you-go” plan and a “flat-rate” plan. This problem is formulated as an online optimization problem extending the ski-rental problem, and analyzed using the competitive ratio. We give a lemma for easily calculating the competitive ratio. Based on the lemma, we derive a family of optimal strategies for a realistic class of instances.
URL: https://globals.ieice.org/en_transactions/information/10.1587/transinf.2015FCP0005/_p

Copy

@ARTICLE{e99-d_3_559,
author={Hiroshi FUJIWARA, Atsushi MATSUDA, Toshihiro FUJITO, },
journal={IEICE TRANSACTIONS on Information},
title={Competitive Analysis for the Flat-Rate Problem},
year={2016},
volume={E99-D},
number={3},
pages={559-566},
abstract={We consider a problem of the choice of price plans offered by a telecommunications company: a “pay-as-you-go” plan and a “flat-rate” plan. This problem is formulated as an online optimization problem extending the ski-rental problem, and analyzed using the competitive ratio. We give a lemma for easily calculating the competitive ratio. Based on the lemma, we derive a family of optimal strategies for a realistic class of instances.},
keywords={},
doi={10.1587/transinf.2015FCP0005},
ISSN={1745-1361},
month={March},}

Copy

TY - JOUR
TI - Competitive Analysis for the Flat-Rate Problem
T2 - IEICE TRANSACTIONS on Information
SP - 559
EP - 566
AU - Hiroshi FUJIWARA
AU - Atsushi MATSUDA
AU - Toshihiro FUJITO
PY - 2016
DO - 10.1587/transinf.2015FCP0005
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E99-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2016
AB - We consider a problem of the choice of price plans offered by a telecommunications company: a “pay-as-you-go” plan and a “flat-rate” plan. This problem is formulated as an online optimization problem extending the ski-rental problem, and analyzed using the competitive ratio. We give a lemma for easily calculating the competitive ratio. Based on the lemma, we derive a family of optimal strategies for a realistic class of instances.
ER -