Online linear optimization over permutations

Shota Yasutake; Kohei Hatano; Shuji Kijima; Eiji Takimoto; Masayuki Takeda

doi:10.1007/978-3-642-25591-5_55

Online linear optimization over permutations

Shota Yasutake, Kohei Hatano, Shuji Kijima, Eiji Takimoto, Masayuki Takeda

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

27 Citations (Scopus)

Abstract

This paper proposes an algorithm for online linear optimization problem over permutations; the objective of the online algorithm is to find a permutation of {1,...,n} at each trial so as to minimize the "regret" for T trials. The regret of our algorithm is O(n ²√T ln n) in expectation for any input sequence. A naive implementation requires more than exponential time. On the other hand, our algorithm uses only O(n) space and runs in O(n ²) time in each trial. To achieve this complexity, we devise two efficient algorithms as subroutines: One is for minimization of an entropy function over the permutahedron P _n , and the other is for randomized rounding over P _n .

Original language	English
Title of host publication	Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Proceedings
Pages	534-543
Number of pages	10
DOIs	https://doi.org/10.1007/978-3-642-25591-5_55
Publication status	Published - 2011
Event	22nd International Symposium on Algorithms and Computation, ISAAC 2011 - Yokohama, Japan Duration: Dec 5 2011 → Dec 8 2011

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	7074 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	22nd International Symposium on Algorithms and Computation, ISAAC 2011
Country/Territory	Japan
City	Yokohama
Period	12/5/11 → 12/8/11

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-642-25591-5_55

Cite this

Yasutake, S., Hatano, K., Kijima, S., Takimoto, E., & Takeda, M. (2011). Online linear optimization over permutations. In Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Proceedings (pp. 534-543). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7074 LNCS). https://doi.org/10.1007/978-3-642-25591-5_55

Online linear optimization over permutations. / Yasutake, Shota; Hatano, Kohei; Kijima, Shuji et al.
Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Proceedings. 2011. p. 534-543 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7074 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Yasutake, S, Hatano, K, Kijima, S, Takimoto, E & Takeda, M 2011, Online linear optimization over permutations. in Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7074 LNCS, pp. 534-543, 22nd International Symposium on Algorithms and Computation, ISAAC 2011, Yokohama, Japan, 12/5/11. https://doi.org/10.1007/978-3-642-25591-5_55

Yasutake S, Hatano K, Kijima S, Takimoto E, Takeda M. Online linear optimization over permutations. In Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Proceedings. 2011. p. 534-543. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-25591-5_55

@inproceedings{89fe2a7ccd494a9b9be3caccd720a826,

title = "Online linear optimization over permutations",

abstract = "This paper proposes an algorithm for online linear optimization problem over permutations; the objective of the online algorithm is to find a permutation of {1,...,n} at each trial so as to minimize the {"}regret{"} for T trials. The regret of our algorithm is O(n 2√T ln n) in expectation for any input sequence. A naive implementation requires more than exponential time. On the other hand, our algorithm uses only O(n) space and runs in O(n 2) time in each trial. To achieve this complexity, we devise two efficient algorithms as subroutines: One is for minimization of an entropy function over the permutahedron P n , and the other is for randomized rounding over P n .",

author = "Shota Yasutake and Kohei Hatano and Shuji Kijima and Eiji Takimoto and Masayuki Takeda",

year = "2011",

doi = "10.1007/978-3-642-25591-5_55",

language = "English",

isbn = "9783642255908",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "534--543",

booktitle = "Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Proceedings",

note = "22nd International Symposium on Algorithms and Computation, ISAAC 2011 ; Conference date: 05-12-2011 Through 08-12-2011",

}

TY - GEN

T1 - Online linear optimization over permutations

AU - Yasutake, Shota

AU - Hatano, Kohei

AU - Kijima, Shuji

AU - Takimoto, Eiji

AU - Takeda, Masayuki

PY - 2011

Y1 - 2011

N2 - This paper proposes an algorithm for online linear optimization problem over permutations; the objective of the online algorithm is to find a permutation of {1,...,n} at each trial so as to minimize the "regret" for T trials. The regret of our algorithm is O(n 2√T ln n) in expectation for any input sequence. A naive implementation requires more than exponential time. On the other hand, our algorithm uses only O(n) space and runs in O(n 2) time in each trial. To achieve this complexity, we devise two efficient algorithms as subroutines: One is for minimization of an entropy function over the permutahedron P n , and the other is for randomized rounding over P n .

AB - This paper proposes an algorithm for online linear optimization problem over permutations; the objective of the online algorithm is to find a permutation of {1,...,n} at each trial so as to minimize the "regret" for T trials. The regret of our algorithm is O(n 2√T ln n) in expectation for any input sequence. A naive implementation requires more than exponential time. On the other hand, our algorithm uses only O(n) space and runs in O(n 2) time in each trial. To achieve this complexity, we devise two efficient algorithms as subroutines: One is for minimization of an entropy function over the permutahedron P n , and the other is for randomized rounding over P n .

UR - http://www.scopus.com/inward/record.url?scp=84055193634&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84055193634&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-25591-5_55

DO - 10.1007/978-3-642-25591-5_55

M3 - Conference contribution

AN - SCOPUS:84055193634

SN - 9783642255908

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 534

EP - 543

BT - Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Proceedings

T2 - 22nd International Symposium on Algorithms and Computation, ISAAC 2011

Y2 - 5 December 2011 through 8 December 2011

ER -

Online linear optimization over permutations

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this