IEICE Technical Report

Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380

Theoretical Foundations of Computing

Workshop Date : 2013-09-03 / Issue Date : 2013-08-27

COMP2013-25
An O(n log n) Algorithm for the Minimax Regret Sink Location Problem in Dynamic Path Networks with the Uniform Capacity
Yuya Higashikawa (Kyoto Univ.), Mordecai J. Golin (HKUST), Naoki Katoh (Kyoto Univ.)
pp. 1 - 8

COMP2013-26
A New UCB-based Algorithm for the Matching-Selection Multi-armed Bandit Problem
Ryo Watanabe, Atsuyoshi Nakamura, Mineichi Kudo (Hokkaido Univ.)
pp. 9 - 16

COMP2013-27
Oracle Pushdown Automata, Nondeterministic Reducibilities, and the Hierarchy over the Family of Context-Free Languages -- (Preliminary Version) --
Tomoyuki Yamakami (Univ. of Fukui)
pp. 17 - 24

COMP2013-28
A Pseudo-Polynomial Algorithm for Mean Payoff Stochastic Games with Perfect Information and a Few Random Positions
Endre Boros (Rutgers Univ.), Khaled Elbassioni (MPI), Vladimir Gurvich (Rutgers Univ.), Kazuhisa Makino (Kyoto Univ.)
p. 25

COMP2013-29
Hardness of Classically Simulating Quantum Circuits with Unbounded Toffoli and Fan-Out Gates
Yasuhiro Takahashi (NTT), Takeshi Yamazaki, Kazuyuki Tanaka (Tohoku Univ.)
pp. 27 - 34

COMP2013-30
Approximation Algorithms for Bandwidth Consective Multicolorings
Yuji Obata, Takao Nishizeki (Kwansei Gakuin Univ.)
pp. 35 - 42

COMP2013-31
Finding Maximum Regular Induced Subgraphs with Prescribed Degree
Yuichi Asahiro (Kyushu Sangyo Univ.), Takehiro Ito (Tohoku Univ.), Hiroshi Eto, Eiji Miyano (Kyushu Inst. of Tech.)
pp. 43 - 50

Note: Each article is a technical report without peer review, and its polished version will be published elsewhere.

The Institute of Electronics, Information and Communication Engineers (IEICE), Japan