TY - JOUR
T1 - Online combinatorial optimization with multiple projections and its application to scheduling problem
AU - Fujita, Takahiro
AU - Hatano, Kohei
AU - Kijima, Shuji
AU - Takimoto, Eiji
N1 - Publisher Copyright:
© 2018 The Institute of Electronics, Information and Communication Engineers.
PY - 2018/9
Y1 - 2018/9
N2 - 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.
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.
UR - http://www.scopus.com/inward/record.url?scp=85053853148&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85053853148&partnerID=8YFLogxK
U2 - 10.1587/transfun.E101.A.1334
DO - 10.1587/transfun.E101.A.1334
M3 - Article
AN - SCOPUS:85053853148
SN - 0916-8508
VL - E101A
SP - 1334
EP - 1343
JO - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
JF - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
IS - 9
ER -