Online Combinatorial Optimization with Multiple Projections and Its Application to Scheduling Problem
Summary :
We consider combinatorial online prediction problems and propose a new construction method of efficient algorithms for the problems. One of the previous approaches to the problem is to apply online prediction method, in which two external procedures the projection and the metarounding are assumed to be implemented. In this work, we generalize the projection to multiple projections. As an application of our framework, we show an algorithm for an online job scheduling problem with a single machine with precedence constraints.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E101-A No.9 pp.1334-1343
- Publication Date
- 2018/09/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E101.A.1334
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
Authors
Takahiro FUJITA
Kyushu University
Kohei HATANO
Kyushu University,RIKEN AIP
Shuji KIJIMA
Kyushu University,JST PRESTO
Eiji TAKIMOTO
Kyushu University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Takahiro FUJITA, Kohei HATANO, Shuji KIJIMA, Eiji TAKIMOTO, "Online Combinatorial Optimization with Multiple Projections and Its Application to Scheduling Problem" in IEICE TRANSACTIONS on Fundamentals,
vol. E101-A, no. 9, pp. 1334-1343, September 2018, doi: 10.1587/transfun.E101.A.1334.
Abstract: We consider combinatorial online prediction problems and propose a new construction method of efficient algorithms for the problems. One of the previous approaches to the problem is to apply online prediction method, in which two external procedures the projection and the metarounding are assumed to be implemented. In this work, we generalize the projection to multiple projections. As an application of our framework, we show an algorithm for an online job scheduling problem with a single machine with precedence constraints.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E101.A.1334/_p
Copy
@ARTICLE{e101-a_9_1334,
author={Takahiro FUJITA, Kohei HATANO, Shuji KIJIMA, Eiji TAKIMOTO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Online Combinatorial Optimization with Multiple Projections and Its Application to Scheduling Problem},
year={2018},
volume={E101-A},
number={9},
pages={1334-1343},
abstract={We consider combinatorial online prediction problems and propose a new construction method of efficient algorithms for the problems. One of the previous approaches to the problem is to apply online prediction method, in which two external procedures the projection and the metarounding are assumed to be implemented. In this work, we generalize the projection to multiple projections. As an application of our framework, we show an algorithm for an online job scheduling problem with a single machine with precedence constraints.},
keywords={},
doi={10.1587/transfun.E101.A.1334},
ISSN={1745-1337},
month={September},}
Copy
TY - JOUR
TI - Online Combinatorial Optimization with Multiple Projections and Its Application to Scheduling Problem
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1334
EP - 1343
AU - Takahiro FUJITA
AU - Kohei HATANO
AU - Shuji KIJIMA
AU - Eiji TAKIMOTO
PY - 2018
DO - 10.1587/transfun.E101.A.1334
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E101-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2018
AB - We consider combinatorial online prediction problems and propose a new construction method of efficient algorithms for the problems. One of the previous approaches to the problem is to apply online prediction method, in which two external procedures the projection and the metarounding are assumed to be implemented. In this work, we generalize the projection to multiple projections. As an application of our framework, we show an algorithm for an online job scheduling problem with a single machine with precedence constraints.
ER -
English
