岩間研究室 発表論文
2006年度
[ 著書 ]
- id=2006-25
- 岩間一雄,
- アルゴリズム・サイエンス: 出口からの超入門,
- 共立出版, 2006年 10月.
[ 論文誌 ]
- id=2006-02
- H. Ito, K. Iwama, and T. Tamura,
- ``Efficient Methods for Determining DNA Probe Orders'',
-
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol.E89-A, no.5, pp.1292--1298, May 2006.
-
-
>> Abstract
- id=2006-03
- K. Sugihara, and H. Ito,
- ``Maximum-Cover Source Location Problems'',
-
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol.E89-A, no.5, pp.1370--1377, May 2006.
-
-
>> Abstract
- id=2006-06
- H. Ito,
- ``Harary's Generalized Ticktacktoe'',
-
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol.J89-A, no.6, pp.458--469, Jun. 2006.
-
-
>> Abstract
- id=2006-17
- M. Hayashi, K. Iwama, H. Nishimura, R. Raymond, and S. Yamashita,
- ``(4,1)-Quantum Random Access Coding does not Exist --- One Qubit is not Enough to Recover One of Four Bits'',
-
New Journal of Physics, vol.8, no.129, Aug. 2006.
-
-
>> Abstract
- id=2006-18
- K. Iwama, S. Miyazaki, and K. Okamoto,
- ``A $(2-c \log N/N)$-Approximation Algorithm for the Stable Marriage Problem'',
-
IEICE Transactions on Information and Systems, vol.E89-D, no.8, pp.2380--2387, Aug. 2006.
-
-
>> Abstract
- id=2006-19
- T. Imamura, K. Iwama, and T. Tsukiji,
- ``Approximated Vertex Cover for Graphs with Perfect Matchings'',
-
IEICE Transactions on Information and Systems, vol.E89-D, no.8, pp.2405--2410, Aug. 2006.
-
-
>> Abstract
- id=2006-21
- M. Yamamoto,
- ``Generating Instances for MAX2SAT with Optimal Solutions'',
-
Theory of Computing Systems, vol.39, no.5, pp.723--742, Sep. 2006.
-
-
>> Abstract
- id=2006-26
- Y. Asahiro, T. Horiyama, K. Makino, H. Ono, T. Sakuma, and M. Yamashita,
- ``How to Collect Balls Moving in the Euclidean Plane'',
-
Discrete Applied Mathematics, vol.154/16, pp.2247--2262, Nov. 2006.
-
-
>> Abstract
- id=2006-27
- Y. Hanatani, T. Horiyama, and K. Iwama,
- ``Density Condensation of Boolean Formulas'',
-
Discrete Applied Mathematics, vol.154/16, pp.2263--2270, Nov. 2006.
-
-
>> Abstract
- id=2006-28
- H. Ito, and H. Nagamochi,
- ``Two Equivalent Measures on Weighted Hypergraphs'',
-
Discrete Applied Mathematics, vol.154/16, pp.2330--2334, Nov. 2006.
-
-
>> Abstract
- id=2006-34
- N. Doi, T. Horiyama, M. Nakanishi, and S. Kimura,
- ``Bit-Length Optimization Method for High-Level Synthesis Based on Non-linear Programming Technique'',
-
IEICE Trans. Fundamentals, vol.E89-A, no.12, pp.3427--3434, Dec. 2006.
- id=2006-41
- T. Riege, J. Rothe, H. Spakowski, and M. Yamamoto,
- ``An Improved Exact Algorithm for the Domatic Number Problem'',
-
Information Processing Letters, vol.101, no.3, pp.101--106, Feb. 2007.
-
-
>> Abstract
- id=2006-44
- D. Avis, and T. Imamura,
- ``A List Heuristic for Vertex Cover'',
-
Operations Research Letters, vol.35/2, pp.201--204, Mar. 2007.
-
-
>> Abstract
[ 国際会議 ]
- id=2006-04
- ※ S. Kato, S. Miyazaki, Y. Nishimura, and Y. Okabe,
- ``Cheat-proof Serverless Network Games'',
-
5th International Conference on Computers and Games (CG 2006), May 2006.
-
-
>> Abstract
- id=2006-05
- K. Sugihara, and H. Ito,
- ``Maximum-Cover Source-Location Problem with Object Edge-Connectivity Three'',
-
Proc. Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2006), pp.131--136, Jun. 2006.
- id=2006-09
- X. Han, K. Iwama, R. Klein, and A. Lingas,
- ``Approximating the Maximum Independent Set and Minimum Vertex coloring on box graphs'',
-
Proc. the 9th Japan-Korea Joint Workshop on Algorithms and Computation (WAAC 2006), pp.33--60, Jul. 2006.
-
-
>> Abstract
- id=2006-10
- A. Ambainis, K. Iwama, A. Kawachi, R. Raymond, and S. Yamashita,
- ``Improved Algorithms for Quantum Identification of Boolean Oracles'',
-
Proc. 10th Scandinavian Workshop on Algorithm Theory (SWAT 2006), LNCS 4059, pp.280--291, Jul. 2006.
-
-
>> Abstract
- id=2006-11
- K. Iwama,
- ``Classic and Quantum Network Coding'',
-
Proc. 10th Scandinavian Workshop on Algorithm Theory (SWAT 2006), LNCS 4059, pp.3--4, Jul. 2006.
-
- (invited talk)
- id=2006-12
- M. Hayashi, K. Iwama, H. Nishimura, R. Raymond, and S. Yamashita,
- ``(4,1)-Quantum Random Access Coding Does Not Exist'',
-
Proc. of IEEE International Symposium on Information Theory (ISIT 2006), pp.446--450, Jul. 2006.
-
-
>> Abstract
- id=2006-13
- T. Riege, J. Rothe, H. Spakowski, and M. Yamamoto,
- ``An Improved Exact Algorithm for the Domatic Number Problem'',
- ICALP06 affiliated workshop: Improving Exponential Time Algorithms (iETA), Jul. 2006.
-
-
>> Abstract
- id=2006-14
- ※ Y. Kiyonari, E. Miyano, and S. Miyazaki,
- ``Computational Complexity Issues in University Interview Timetabling'',
-
Proc. the 6th International Conference on the Practice and Theory of Automated Timetabling (PATAT 2006), pp.448--453, Aug. 2006.
- id=2006-15
- O. Watanabe, and M. Yamamoto,
- ``Average-Case Analysis for the MAX-2SAT Problem'',
-
Proc. Theory and Applications of Satisfiability Testing (SAT06), pp.277-282, Aug. 2006.
-
-
>> Abstract
- id=2006-16
- K. Iwama, and H. Morizumi,
- ``Reductions for Monotone Boolean Circuits'',
-
Proc. the 31st International Symposium on Mathematical Foundations of Computer Science (MFCS 2006), LNCS 4162, pp.540--548, Aug. 2006.
-
-
>> Abstract
- id=2006-22
- X. Han, D. Ye, and Y. Zhou,
- ``Improved Online Hypercube Packing'',
- Proc. the 4th International Workshop on Approximation and Online
Algorithms (WAOA 2006), LNCS 4368, pp.226--239, Sep. 2006.
-
-
>> Abstract
- id=2006-29
- T. Horiyama, K. Iwama, and J. Kawahara,
- ``Finite-State Online Algorithms and Their Automated Competitive Analysis'',
- Proc. the 17th International Symposium on Algorithms and
Computation (ISAAC 2006), LNCS 4288, pp.71--80, Dec. 2006.
-
-
>> Abstract
- id=2006-30
- K. Iwama, H. Morizumi, and J. Tarui,
- ``Negation-Limited Complexity of Parity and Inverters'',
-
Proc. the 17th International Symposium on Algorithms and Computation (ISAAC 2006), LNCS 4288, pp.223--232, Dec. 2006.
-
-
>> Abstract
- id=2006-31
- K. Iwama,
- ``Stable Matching Problems'',
- Proc. the 17th International Symposium on algorithms and
Computation (ISAAC 2006), LNCS 4288, pp.1, Dec. 2006.
-
- (invited talk)
- id=2006-38
- N. Bansal, X. Han, K. Iwama, M. Sviridenko, and G. Zhang,
- ``Harmonic Algorithm for 3-Dimensional Strip Packing Problem'',
-
Proc. 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), pp.1197--1206, Jan. 2007.
-
-
>> Abstract
- id=2006-39
- K. Iwama, S. Miyazaki, and N. Yamauchi,
- ``A 1.875-Approximation Algorithm for the Stable Marriage
Problem'',
- Proc. 18th ACM-SIAM Symposium on Discrete Algorithms (SODA
2007), pp.288--297, Jan. 2007.
-
-
>> Abstract
- id=2006-40
- ※ Y. Asahiro, E. Miyano, S. Miyazaki, and T. Yoshimuta,
- ``Weighted Nearest Neighbor Algorithms for the Graph Exploration
Problem on Cycles'',
- Proc. 33rd Conference on Current Trends in Theory and Practice of
Informatics (SOFSEM 2007), LNCS 4362, pp.164--175, Jan. 2007.
-
-
>> Abstract
- id=2006-42
- M. Hayashi, K. Iwama, H. Nishimura, R. Raymond, and S. Yamashita,
- ``Quantum Network Coding'',
- Proc. 24th International Symposium on Theoretical Aspects
of Computer Science (STACS 2007), LNCS 4393, pp.610--621, Feb. 2007.
- id=2006-43
- H. Fujiwara, K. Iwama, and K. Yonezawa,
- ``Online Chasing Problems for Regular $n$-Gons'',
-
The 5th International Conference on Research, Innovation and Vision for the Future (RIVF2007), pp.36--41, Mar. 2007.
-
-
>> Abstract
- id=2006-48
- J. Akiyama, H. Fukuda, H. Ito, and G. Nakamura,
- ``Infinite series of generalized Gospher space filling curves'',
- Proc. the China-Japan Joint Conference on Discrete
Geometry and Graph Theory (CJCDGCGT 2005), LNCS 4381, pp.1--9, Mar. 2007.
- id=2006-49
- H. Ito,
- ``Impossibility of transformation of vertex labeled simple
graphs preserving the cut-size order'',
- Proc. the China-Japan Joint Conference on Discrete Geometry
and Graph Theory (CJCDGCGT 2005), LNCS 4381, pp.59--69, Mar. 2007.
[ 国内発表 ]
- id=2006-07
- K. Iwama, and H. Morizumi,
- ``Reductions for Monotone Boolean Circuits'',
- 電子情報通信学会 コンピュテーション研究会, 信学技報, vol.106, no.128, COMP2006-19, pp.15--19, Jun. 2006.
-
-
>> Abstract
- id=2006-08
- ※ 清成悠貴, 宮野英次, 宮崎修一,
- ``試問予定表作成問題の計算複雑さ'',
- 電子情報通信学会 コンピュテーション研究会, 信学技報, vol.106, no.128, COMP2006-18, pp.7--14, 2006年 6月.
-
-
>> Abstract
- id=2006-20
- T. Horiyama, K. Iwama, and K. Seto,
- ``Constant Depth Circuits for Symmetric Boolean Functions'',
- 夏のLAシンポジウム, pp.20.1--20.4, Aug. 2006.
-
-
>> Abstract
- id=2006-23
- ※ 吉牟田拓朗, 宮野英次, 宮崎修一,
- ``オンラインTSPアルゴリズムに対する下限について'',
- 平成18年度 第59回電気関係学会九州支部連合大会, 10-2A-07, pp.342, 2006年 9月.
-
-
>> Abstract
- id=2006-24
- 堀山貴史,
- ``3彩色不能な平面グラフの構成'',
- 列挙アルゴリズム合宿, 2006年 9月.
- id=2006-32
- ※ 朝廣雄一, 宮野英次, 宮崎修一, 吉牟田拓朗,
- ``サイクルグラフ上での地図作成問題に対する重み付き最近傍アルゴリズム'',
- 電子情報通信学会コンピュテーション研究会, 信学技報, vol.106, no.405, COMP2006-43, pp.15--22, 2006年 12月.
-
-
>> Abstract
- id=2006-33
- 山内直哉, 宮崎修一, 岩間一雄,
- ``安定結婚問題に対する1.875-近似アルゴリズム'',
- 電子情報通信学会コンピュテーション研究会, 信学技報, vol.106, no.405, COMP2006-48, pp.49--56, 2006年 12月.
-
-
>> Abstract
- id=2006-35
- H. Morizumi, and J. Tarui,
- ``Linear-Size Log-Depth Negation-Limited Inverter for k-tonic
0/1 Sequences'',
- 電子情報通信学会コンピュテーション研究会, 信学技報, vol.106, no.405, COMP2006-49, pp.57--60, Dec. 2006.
-
-
>> Abstract
- id=2006-36
- 森住 大樹, 垂井 淳, 岩間 一雄,
- ``Negation-Limited Complexity of Parity and Inverters'',
- 冬のLAシンポジウム, 京都大学数理解析研究所講究録, pp.21.1--21.9, 2007年 1月.
-
-
>> Abstract
- id=2006-37
- 中島拓也, 岩間一雄,
- ``Improvement of the Algorithm for the Traveling Salesman
Problem on Cubic Graphs'',
- 冬のLAシンポジウム, 京都大学数理解析研究所講究録, pp.23.1--23.8, 2007年 1月.
-
-
>> Abstract
- id=2006-47
- 山内直哉, 宮崎修一, 岩間一雄,
- ``安定結婚問題に対する1.8-近似アルゴリズム'',
- 電子情報通信学会総合大会講演論文集, pp.DS-1--3, 2007年 3月.
-
-
>> Abstract
[ 解説 ]
- id=2006-01
- ※ 宮崎修一,
- ``ルータ上のバッファ管理問題に対するオンラインアルゴリズム'',
- 電子情報通信学会誌, vol.89, no.4, pp.299--303, 2006年 4月.
-
-
>> Abstract
Abstract
-
id=2006-01
- ネットワーク上で輻輳が起こった際に,
ルータは到着するパケットを全て処理しきれない場合がある.
このとき,パケットの取捨選択やバッファの管理をいかに行うかが,
QoS(Quality of Service)保証においては重要となる.
近年,この問題をオンライン問題として定式化し,
オンラインアルゴリズムの競合比解析を行う研究が盛んに行われている.
本稿ではこれらの結果を紹介する.
-
id=2006-02
- In STS-based mapping, it is necessary to obtain the correct
order of probes in a DNA sequence from a given set of fragments
or an equivalently a hybridization matrix $A$. It is well-known
that the problem is formulated as the combinatorial problem of
obtaining a permutation of $A$'s columns so that the resulting
matrix has a consecutive-one property. If the data (the hybridization
matrix) is error free and includes enough information,
then the above column order uniquely determines the correct
order of the probes. Unfortunately this does not hold
if the data include errors, and this has been a popular research target
in computational biology. Even if there is no error, ambiguities
in the probe order may still remain. This in fact happens because
of the lack of some information regarding the data, but almost
no further investigation has previously been made. In this paper,
we define a measure of such imperfectness of the data as the
minimum amount of the additional fragments that are needed to
uniquely fix the probe order. Polynomial-time algorithms to compute
such additional fragments of the minimum cost are presented.
A computer simulation using genes of human chromosome 20
is also noted.
-
id=2006-03
- Given a graph $G=(V,E)$, a set of vertices $S \subseteq V$
covers $v \in V$ if the edge connectivity between $S$ and $v$ is
at least a given number $k$. Vertices in $S$ are called sources.
The source location problem is a problem of finding a minimum-size
source set covering all vertices of a given graph.
This paper presents a new variation of the problem,
called maximum-cover source-location problem,
which finds a source set $S$ with a given size $p$,
maximizing the sum of the weight of vertices covered by $S$.
It presents an $O(np + m + n\log n)$-time algorithm for $k=2$,
where $n=|V|$ and $m=|E|$. Especially it runs linear time
if $G$ is connected. This algorithm uses a subroutine for finding
a subtree with the maximum weight among $p$-leaf trees of a given
vertex-weighted tree. For the problem we give a greedy-based
linear-time algorithm, which is an extension of the linear-time
algorithm for finding a longest path of a given tree presented
by E.~W.~Dijkstra around 1960. Moreover, we show some polynomial
solvable cases, e.g., a given graph is a tree or $(k-1)$-edge-connected,
and NP-hard cases, e.g., a vertex-cost function is given or $G$ is a
digraph.
-
id=2006-04
- We consider playing online games on peer-to-peer networks, without
assuming servers that control the execution of a game. In such an
environment, players may cheat the opponent by, for example, illegally
replacing the cards in their hands. The aim of this paper is to
examine a possibility of excluding such cheatings. We show that by
employing cryptographic techniques, we can exclude some types of
cheating at some level. Finally, based on our discussion, we
implement cheat-proof network ``Gunjin-Shogi'', which is a variant of
Japanese Chess.
-
id=2006-06
- The generalized ticktacktoe, presented by F. Harary, is a game
that two players put a stone on a given square grid board alternately
and one who make a given animal (figure) by his or her stones first is
the winner. For any animal, if the both players play optimally, the
first player wins (the animal is a winner) or the game is brought to a
draw (the animal is a loser). The problem which animals are winners or
losers have been investigated and have been solved for many
animals. This paper surveys the results, techniques, and open problems
of the game, and discusses directions of feature work.
-
id=2006-07
- The large class, say {\it NLOG}, of Boolean functions,
including 0-1 Sort and 0-1 Merge, have an upper bound of $O(n\log n)$
for their monotone circuit size, i.e., have circuits with
$O(n\log n)$ AND/OR gates of fan-in two. Suppose that we can use,
besides such normal AND/OR gates, any number of more powerful
``$F$-gates'' which realize a monotone Boolean function
$F$ with $r (\geq 2)$ inputs and $r' (\geq 1)$ outputs.
Note that the cost of each AND/OR gate is one and we assume that
the cost of each $F$-gate is $r$. Now we define: A Boolean function $f$
in NLOG is said to be $F$-Easy if $f$ can be computed by a circuit
with AND/OR/$F$ gates whose total cost is $o(n\log n)$.
In this paper we show that 0-1 Merge is not $F$-Easy for an arbitrary
monotone function $F$ such that $r' \leq r/\log r$.
-
id=2006-08
- 本稿では,試問予定表作成問題と呼ばれる大学における
時間割表作成問題を導入する.この問題では,ある決まった数の審査員,
例えば3人の審査員が$2n$人の学生にそれぞれ割り当てられる.
それらの学生と担当審査員の組は,$n$個の時刻と2つの部屋から成る
$n\times 2$行列に割り当てられる必要がある.
ここで,同じ審査員が担当する異なる2人の学生は異なる時刻に
割り当てられなければならない.さらに,
すべての審査員が2つの部屋を移動する回数の合計をできるだけ少なくした.
これは,実際に京都大学の試問予定表作成において発生した問題である.
この問題について2つの制約付きモデルを提案し,
それらの計算複雑さについて調査する.
-
id=2006-09
- A box graph is the intersection graph of a finite set
of orthogonal rectangles in the plane. The problem of whether
or not the maximum independent set problem (MIS for short) for
box graphs can be approximated within a substantially sub-logarithmic
factor in polynomial time has been open for several years.
We show that for box graphs on $n$ vertices which have an
independent set of size $\Omega(n/\log^{O(1)}n)$ the maximum
independent set problem can be approximated within
$O(\log n / \log \log n)$ in polynomial time. Furthermore,
we show that the chromatic number of a box graph on $n$ vertices
is within an $O(\log n)$ factor from the size of its maximum clique
and provide an $O(\log n)$ approximation algorithm for minimum vertex
coloring of such a box graph. More generally, we can show that
the chromatic number of the intersection graph of $n$ $d$-dimensional
orthogonal rectangles is within an $O(\log^{d-1}n)$ factor from
the size of its maximum clique and obtain an $O(\log^{d-1}n)$
approximation algorithm for minimum vertex coloring
of such an intersection graph.
-
id=2006-10
- The oracle identification problem (OIP) was introduced by Ambainis
et al. [3]. It is given as a set $S$ of $M$ oracles and a blackbox
oracle $f$. Our task is to figure out which oracle in $S$ is equal to
the blackbox $f$ by making queries to $f$. OIP includes several problems
such as the Grover Search as special cases. In this paper, we improve
the algorithms in [3] by providing a mostly optimal upper bound of query
complexity for this problem: (i) For any oracle set $S$ such that
$|S|\leq 2^{N^d} ~(d < 1)$, we design an algorithm whose query
complexity is, $O(\sqrt{N\log N/\log N })$ matching the lower bound
proved in [3]. (ii) Our algorithm also works for the range between
$2^{N^d}$ and $2^{N/\log N}$ (where the bound becomes $O(N)$), but the
gap between the upper and lower bounds worsens gradually. (iii) Our
algorithm is robust, namely, it exhibits the same performance (up to a
constant factor) against the noisy oracles as also shown in the
literatures [2, 11, 18] for special cases of OIP.
-
id=2006-12
- An $(n,1,p)$-Quantum Random Access (QRA) coding, introduced by
Ambainis, Nayak, Ta-shma and Vazirani in ACM Symp. on Theory of
Computing 1999, is the following communication system: The sender which
has $n$-bit information encodes his/her information into one qubit,
which is sent to the receiver. The receiver can recover any one bit of
the original $n$ bits correctly with probability at least $p$, through a
certain decoding process based on positive operator-valued
measures. Actually, Ambainis et al. shows the existence of a
(2,1,0.85)-QRA coding and also proves the impossibility of its classical
counterpart. Chuang immediately extends it to a (3,1,0.79)-QRA coding
and whether or not a $(4,1,p)$-QRA coding such that $p > 1/2$ exists has
been open since then. This paper gives a negative answer to this open
question.
-
id=2006-13
- The 3-domatic number problem asks whether a given graph
can be partitioned into three dominating sets.
We prove that this problem can be solved by a deterministic algorithm
in time $2.695n$ (up to polynomial factors) and in polynomial space.
This result improves the previous bound of $2.8805n$,
which is due to Fomin, Grandoni, Pyatkin, and Stepanov.
To prove our result, we combine an algorithm by Fomin et al. with
Yamamoto's algorithm for the satisfiability problem. In addition,
we show that the 3-domatic number problem can be solved
for graphs $G$ with bounded maximum degree $\Delta (G)$
by a randomized polynomial-space algorithm,
whose running time is better than the previous bound
due to Riege and Rothe whenever $\Delta (G) \geq 5$.
Our new randomized algorithm employs Sch\''oning's approach
to constraint satisfaction problems.
-
id=2006-15
- We propose a ``planted solution model''
for discussing the average-case complexity of the MAX-2SAT problem.
We show that for a large range of parameters,
the planted solution (more precisely, one of the planted solution pair)
is the optimal solution for the generated instance with high probability.
We then give a simple linear time algorithm based on a message passing
method, and we prove that it solves the MAX-2SAT problem with high
probability under our planted solution model.
-
id=2006-16
- The large class, say {\it NLOG}, of Boolean functions,
including 0-1 Sort and 0-1 Merge, have an upper bound of $O(n\log n)$
for their monotone circuit size, i.e., have circuits with $O(n\log n)$
AND/OR gates of fan-in two. Suppose that we can use, besides such
normal AND/OR gates, any number of more powerful ``$F$-gates''
which realize a monotone Boolean function $F$ with $r (\geq 2)$ inputs
and $r' (\geq 1)$ outputs. Note that the cost of each AND/OR gate is
one and we assume that the cost of each $F$-gate is $r$. Now we define:
A Boolean function $f$ in NLOG is said to be $F$-Easy if $f$ can be
constructed by a circuit with AND/OR/$F$ gates whose total cost is
$o(n\log n)$. In this paper we show that 0-1 Merge is not $F$-Easy
for an arbitrary monotone function $F$ such that $r' \leq r/\log r$.
-
id=2006-17
- An $(n,1,p)$-quantum random access (QRA) coding, introduced by
Ambainis et al (1999 {\em ACM Symp. Theory of Computing} p 376), is the
following communication system: the sender which has n-bit information
encodes his/her information into one qubit, which is sent to the
receiver. The receiver can recover any one bit of the original n bits
correctly with probability at least p, through a certain decoding
process based on positive operator-valued measures. Actually, Ambainis
et al shows the existence of a (2,1,0.85)-QRA coding and also proves the
impossibility of its classical counterpart. Chuang immediately extends
it to a (3,1,0.79)-QRA coding and whether or not a (4,1,$p$)-QRA coding
such that $p > 1/2$ exists has been open since then. This paper gives
a negative answer to this open question. Moreover, we generalize its
negative answer for one-qubit encoding to the case of multiple-qubit
encoding.
-
id=2006-18
- An instance of the classical stable marriage problem requires all
participants to submit a strictly ordered preference list containing
all members of the opposite sex. However, considering applications in
real-world, we can think of two natural relaxations, namely,
incomplete preference lists and ties in the lists. Either variation
leaves the problem polynomially solvable, but it is known that finding
a maximum cardinality stable matching is NP-hard when both variations
are allowed.
It is easy to see that the size of any two stable matchings differ by
at most a factor of two, and so, an approximation algorithm with a
factor two is trivial. A few approximation algorithms have been
proposed with approximation ratio better than two, but they are only
for restricted instances, such as restricting occurrence of ties
and/or lengths of ties. Up to the present, there is no known
approximation algorithm with ratio better than two for general inputs.
In this paper, we give the first nontrivial result for approximation
of factor less than two for general instances. Our algorithm achieves
the ratio $2-c\frac{\log N}{N}$ for an arbitrarily positive constant
$c$, where $N$ denotes the number of men in an input.
-
id=2006-19
- Chen and Kanj considered the VERTEX COVER problem for graphs with
perfect matchings (VC-PM). They showed that: (i) There is a reduction
from general VERTEX COVER to VC-PM, which guarantees that if one can
achieve an approximation factor of less than two for VC-PM, then one can
do so for general VERTEX COVER as well. (ii) There is an algorithm for
VC-PM whose approximation factor is given as $1.069 + 0.069d$ where $d$
is the average degree of the given graph. In this paper we improve
(ii). Namely we give a new VC-PM algorithm which greatly outperforms the
above one and its approximation factor is roughly $2-6.74/d + 6.28$. Our
algorithm also works for graphs with "large" matchings, although its
approximation factor is degenerated.
-
id=2006-20
- We consider $\Sigma_d$ circuits of unbounded fan-in, whose depth is
constant $d$ and the top gate is an OR. We prove that any symmetric
Boolean function has a $\Sigma_d$ circuit of size at most
$2^{O(n^{1/(d-1)})}$ where $n$ is the number of the variables. This
result is obtained by showing the upper bound
$2^{k^{1/(d-2)}}(1+1/k)^{n+O(\log n)}$ on $\Sigma^k_d$ circuits, in
which the bottom fan-in is bounded by $k$.
-
id=2006-21
- A test instance generator (an instance generator for short)
for MAX2SAT is a procedure that produces, given a number $n$ of variables,
a 2-CNF formula $F$ of $n$ variables (randomly chosen from
some reasonably large domain), and simultaneously provides
one of the optimal solutions for $F$. We propose an outline to design
an instance generator using an expanding graph of a certain type,
called here an ``exact $1/2$-enlarger''. We first show a simple
algorithm for constructing an exact $1/2$-enlarger,
thereby deriving one concrete polynomial-time instance generator GEN.
We also show that an exact $1/2$-enlarger can be obtained with
high probability from graphs randomly constructed. From this fact,
we propose another type of instance generator RGEN;
it produces a 2-CNF formula with a solution
which is optimal for the formula with high probability.
However, RGEN produces less structured formulas
and a much larger class of formulas than GEN.
In fact, we prove the NP-hardness of MAX2SAT over
the set of 2-CNF formulas produced by RGEN.
-
id=2006-22
- In this paper, we study online multidimensional bin packing
problem when all items are hypercubes. Based on the techniques in
one dimensional bin packing algorithm Super Harmonic by Seiden,
we give a framework for online hypercube packing problem
and obtain new upper bounds of asymptotic competitive ratios.
For square packing, we get an upper bound of 2.1439, which is better
than 2.24437. For cube packing, we also give a new upper bound 2.6852
which is better than 2.9421 by Epstein and van Stee.
-
id=2006-23
- 本稿では,代表的な最適化問題の1つである巡回セールスパーソン問題
(Traveling Salesperson Problem,以下TSP)のオンライン版であるオンライン
TSPを考える.通常のTSPは,入力であるグラフ$G=(V, E, w)$ ($V$は頂点集合,
$E$は辺集合,$w$は辺重み)が予め与えられたとき,全ての頂点を最低一回ずつ
訪問し,出発点に戻る巡回路で辺重みの総和を最小にするものを求めることを目
的とする.オンラインTSPでは,新しい頂点を訪れると,その頂点と隣接する全
ての頂点間の辺とそれらの辺重みの情報が新たに分かる.このような条件の下で
巡回路の辺重みの総和をできるだけ小さくすることを目的とする.
オンラインアルゴリズムは競合比によって評価される.任意の入力$G$に対する
オンラインアルゴリズムALGの出力を$ALG(G)$,オフラインアルゴリズムの最適
解を$OPT(G)$としたとき,$\frac{ALG(G)}{OPT(G)}\leq \alpha$が成り立つとき,
ALGの競合比が$\alpha$であると言う.すなわち,$\alpha$の値が1に近いほど良
いアルゴリズムになる.オンラインTSPに対しては,競合比が16 のアルゴリズム
(ShortCut)が知られているが\cite{1},下限例に関してはあまり議論されてい
ない.本稿では,ShortCutに対する6競合比の下限例を示し,さらにはオンライ
ンTSPに対する1.25 競合比の下限例を示す.
-
id=2006-26
- In this paper, we study how to collect $n$ balls moving with
a fixed constant velocity in the Euclidean plane by $k$ robots
moving on straight track-lines through the origin. Since all
the balls might not be caught by robots, differently from
Moving-target TSP, we consider the following 3 problems in
various situations: (i) deciding if $k$ robots can collect
all $n$ balls; (ii) maximizing the number of the balls collected
by $k$ robots; (iii) minimizing the number of the robots to
collect all $n$ balls. The situations considered in this paper
contain the cases in which track-lines are given (or not),
and track-lines are identical (or not). For all problems and
situations, we provide polynomial time algorithms or proofs
of intractability, which clarify the tractability-intractability
frontier in the ball collecting problems in the Euclidean plane.
-
id=2006-27
- We consider problems of reasoning with a knowledge-base, which is
represented by an ordered binary decision diagram (OBDD), for two
cases of general and Horn knowledge-bases. Our main results say
that both finding a model of a knowledge-base and deducing from a
knowledge-base can be done in linear time for a general knowledge-base,
but that abduction is NP-complete even for a Horn knowledge-base.
Then, we consider abduction when its assumption set consists
of all propositional literals (i.e., an answer for a given query
is allowed to include any positive literals), and show that it can
be done in polynomial time if the knowledge-base is Horn, while it
remains NP-complete for the general case. Some other solvable cases
are also discussed.
-
id=2006-28
- Let $H=(N,E,w)$ be a hypergraph with a node set $N=\{ 0,1,\ldots
,n-1\}$, a hyperedge set $E\subseteq 2^N$, and real edge-weights $w(e)$
for $e\in E$. Given a convex $n$-gon $P$ in the plane with vertices
$x_0,x_1,\ldots ,x_{n-1}$ which are arranged in this order clockwisely,
let each node $i\in N$ correspond to the vertex $x_i$ and define the
area $A_P(H)$ of $H$ on $P$ by the sum of the weighted areas of convex
hulls for all hyperedges in $H$. For $0\le i < j < k\le n-1$,
a convex
three-cut $C(i,j,k)$ of $N$ is $\{\{ i,\ldots ,j-1\} , \{ j,\ldots
,k-1\} , \{ k,\ldots ,n-1,0,\ldots ,i-1\}\}$ and its size $c_H(i,j,k)$
in $H$ is defined as the sum of weights of edges eE such that e contains
at least one node from each of $\{ i,\ldots ,j-1\}$, $\{ j,\ldots
,k-1\}$ and $\{ k,\ldots ,n-1,0,\ldots ,i-1\}$. We show that the
following two conditions are equivalent: \\
$\cdot$ $A_P(H)\le A_P(H')$ for all convex $n$-gons $P$.\\\\
$\cdot$ $c_H(i,j,k)c'_H$ $(i,j,k)$ for all convex three-cuts $C(i,j,k)$.\\\\
From this property, a polynomial time algorithm for determining whether
or not given weighted hypergraphs $H$ and $H'$ satisfy $``A_P(H)\leq
A_P(H')''$ for all convex $n$-gons $P''$ is immediately obtained.
-
id=2006-29
- In this paper we study the Revocable Online Knapsack Problem
(ROKP) which is an extension of the Online Knapsack Problem. We prove
an optimal upper bound of $1/t$ for the competitive ratio of ROKP,
where $t$ is a real root of $4x^3 + 5x^2 - x - 4 = 0$ ($t \approx
0.76850$ and $1/t \approx 1.3012$). To prove this result, we made a
full use of computer programs as follows: For the base algorithm that
is designed in a conventional manner, we first construct an equivalent
finite state diagram with about 300 states. Then for each state,
we generate a finite set of inequalities such that the competitive
ratio at that state is at most $1/t$ if the set of inequalities do
not have a real solution. The latter can be checked by Mathematica.
The number of inequalities generated was approximately 600 in total,
and our computation time was 30 minutes using Athlon XP 2600+.
-
id=2006-30
- We give improved lower bounds for the size of negation-limited
circuits computing Parity and for the size of negation-limited
inverters. An inverter is a circuit with inputs $x_1,\ldots,x_n$
and outputs $\neg x_1,\ldots,\neg x_n$. We show that~(1) For $n=2^r-1$,
circuits computing Parity with $r-1$ NOT gates have size at least
$6n-\log_2(n+1)-O(1)$ and (2) For $n=2^r-1$, inverters with $r$ NOT
gates have size at least $8n-\log_2(n+1)-O(1)$. We derive our bounds
above by considering the minimum size of a circuit with at most
$r$ NOT gates that computes Parity for {\em sorted\/} inputs
$x_1\geq\cdots\geq x_n$. For an {\em arbitrary\/} $r$, we completely
determine the minimum size. For odd~$n$, it is $2n-r-2$ for
$\lceil \log_2(n+1)\rceil-1\leq r \leq n/2$, and it is
$\lfloor 3/2 \: n\rfloor-1$ for $r \geq n/2$. We also determine the
minimum size of an {\em inverter for sorted inputs\/}
with at most $r$ NOT gates. It is $4n-3r$ for
$\lceil \log_2(n+1) \rceil \leq r \leq n$. In particular,
the negation-limited inverter for sorted inputs due to
Fischer, which is a core component in all the known
constructions of negation-limited inverters, is shown to have
the minimum possible size. Our fairly simple lower bound proofs
use gate elimination arguments.
-
id=2006-32
- グラフ上での地図作成問題とは,探索者が未知のグラフの全ての頂点を訪
問することによりグラフ構造を調査する問題である.探索者は辺の存在とその長
さをその端点を訪れるまで判らないとする.探索者は,できるだけ短い経路を通
ることにより全ての頂点と辺を調査して,出発点まで戻って来なければならない.
本問題に対する最も単純な方法の一つは,最近傍アルゴリズム({\sf NN}) であ
り,まだ訪れていない頂点の中で探索者の現在の場所から最も近い場所に移動す
る戦略である.重み付き最近傍アルゴリズム({\sf WNN})は,{\sf NN}の拡張で
あり,ある重み付きの距離により次の移動場所を決める.平面グラフにおいては,
重み$3$である{\sf WNN}が$16$競合であることが知られている.本稿ではサイク
ルグラフについては,{\sf NN} の競合比が$1.5$となること,その解析が厳密で
あることを示す.また,サイクルグラフに対しては{\sf WNN}の中で{\sf NN}が
最適であることを示す.さらに,本問題に対しては,$1.25$競合よりも良いアル
ゴリズムが存在しないことを示す.
-
id=2006-33
- 安定結婚問題において,同順位リストと不完全リストの存在を許した問題
に対して最大サイズの安定マッチングを見つける問題を考える.この問題はNP困
難であり,現在知られている中で最も良い近似アルゴリズムは,
($2-c\frac{1}{\sqrt{N}}$)-近似アルゴリズムである.(ここで,$c$は$c
\leq \frac{1}{4 \sqrt{6}}$を満たす正定数であり,$N$は入力中の男性の数で
ある.)本論文では,この近似度を$1.875$に改良した.
-
id=2006-35
- A binary sequence $x_1, \ldots, x_n$ is called $k$-tonic if for $1
\leq i \leq n-1$ the number of $i$'s such that $x_i \neq x_{i+1}$ is at
most $k$. In this paper, we give the construction of a circuit inverting
$k$-tonic sequences, which has size $O((\log k) \cdot n)$ depth $O((\log
k) \cdot \log \log n + \log n)$ and contains $\log_2 n + O(\log\log n)$
NOT gates. Our construction improves all parameters of the construction
by Sato, Amano and Maruoka, whose size is $O(kn)$ and depth is
$O(k\log^{2}n)$ using $O(k\log n)$ NOT gates. If $k = O(1)$, the
previous construction needs $O(\log^{2}n)$ depth, but our inverter has
linear size and log depth using $O(\log n)$ NOT gates. Beals, Nishino
and Tanaka have shown the construction of a size $O(n\log n)$ depth
$O(\log n)$ inverter for all sequences with $\lceil \log_2(n+1) \rceil$
NOT gates. If $k=n^{o(1)}$, our construction reduces the size to
$o(n\log n)$ with the same depth and only $O(\log\log n)$ increase of
the number of NOT gates. Our idea on the construction of an inverter for
$k$-tonic sequences also give an improvement for a circuit sorting
$k$-tonic sequences from the construction by Sato, Amano and
Maruoka.
-
id=2006-36
- In {\em negation-limited\/} complexity, one considers circuits
with a limited number of NOT gates, being motivated by the gap in our
understanding of monotone versus general circuit complexity, and hoping
to better understand the power of NOT gates. We give improved lower
bounds for the size (the number of AND/OR/NOT) of negation-limited
circuits computing Parity and for the size of negation-limited
inverters. An {\em inverter\/} is a circuit with inputs $x_1,\ldots,x_n$
and outputs $\neg x_1,\ldots,\neg x_n$. We show that (a) For $n=2^r-1$,
circuits computing Parity with $r-1$ NOT gates have size at least
$6n-\log_2(n+1)-O(1)$, and (b) For $n=2^r-1$, inverters with $r$ NOT
gates have size at least $8n-\log_2(n+1)-O(1)$. We derive our bounds
above by considering the minimum size of a circuit with at most $r$ NOT
gates that computes Parity for {\em sorted\/} inputs $x_1\geq\cdots\geq
x_n$. For an {\em arbitrary\/} $r$, we completely determine the minimum
size. It is $2n-r-2$ for odd~$n$ and $2n-r-1$ for even~$n$ for $\lceil
\log_2(n+1)\rceil-1\leq r \leq n/2$, and it is $\lfloor 3/2 \:
n\rfloor-1$ for $r \geq n/2$. We also determine the minimum size of an
{\em inverter for sorted inputs\/} with at most~$r$ NOT gates. It is
$4n-3r$ for $\lceil \log_2(n+1) \rceil \leq r \leq n$. In particular,
the negation-limited inverter for sorted inputs due to Fischer, which is
a core component in all the known constructions of negation-limited
inverters, is shown to have the minimum possible size. Our fairly simple
lower bound proofs use gate elimination arguments in a somewhat novel
way.
-
id=2006-37
- 本発表では, $n$頂点の cubic graphs, あるいは次数3以下のグラフにお
いて巡回セールスマン問題が$O(1.2569^n)$時間で解く事ができることを示す.
これは同じく$n$頂点 cubic graphsにおけるTSPが$O(2^{n/3}) \approx
1.2599^n$で解けることを示したEppsteinの論文の改良である. 探索中における
内部の状態を考慮にいれ,最悪の場合が高々$7n/24$回しかおきないように
Eppsteinのアルゴリズムを変更することで計算量を改善した.
-
id=2006-38
- In the three dimensional strip packing problem, we are given a set
of three-dimensional rectangular items $I=\{(x_i,y_i,z_i):i=1,\dots,n\}$
and a three dimensional box $B$. The goal is to pack all the items in
the box $B$ without any overlap, such that the height of the packing is
minimized. We consider the most basic version of the problem, where the
items must be packed with their edges parallel to the edges of $B$ and
cannot be rotated.
Building upon Caprara's work for the two dimensional bin
packing problem we obtain an approximation algorithm with a
similar performance guarantee of $T_{\infty}\approx 1.69$ where
$T_{\infty}$ is the well known Harmonic number that occurs
naturally in the context of bin packing. The previously known
approximation algorithms for this problem had worst case
performance guarantees of 2, 2.64, 2.67, 2.89 and 3.25.
Our second algorithm is an asymptotic PTAS for the case in which
all items have {\em square} bases.
-
id=2006-39
- We consider the problem of finding a stable matching of maximum
size when both ties and unacceptable partners are allowed in preference
lists. This problem is known to be APX-hard, and the current best known
approximation algorithm achieves the approximation ratio
$2-c\frac{1}{\sqrt{N}}$, where $c$ is some positive constant. In this
paper, we give a 1.875--approximation algorithm, which is the first
result on the approximation ratio better than two.
-
id=2006-40
- In the graph exploration problem, a searcher explores the whole
set of nodes of an unknown graph. The searcher is not aware of the
existence of an edge until he/she visits one of its endpoints. The
searcher's task is to visit all the nodes and go back to the starting
node by traveling as a short tour as possible. One of the simplest
strategies is the nearest neighbor algorithm ({\sf NN}), which always
chooses the unvisited node nearest to the searcher's current position.
The weighted {\sf NN} ({\sf WNN}) is an extension of {\sf NN}, which
chooses the next node to visit by using the weighted distance. It is
known that {\sf WNN} with weight 3 is $16$-competitive for planar
graphs. In this paper we prove that {\sf NN} achieves the competitive
ratio of $1.5$ for cycles. In addition, we show that the analysis for
the competitive ratio of {\sf NN} is tight by providing an instance for
which the bound of 1.5 is attained, and {\sf NN} is the best for cycles
among {\sf WNN} with all possible weights. Furthermore, we prove that no
online algorithm is better than $1.25$-competitive.
-
id=2006-41
- The 3-domatic number problem asks whether a given graph
can be partitioned into three dominating sets.
We prove that this problem can be solved by a deterministic algorithm
in time $2.695n$ (up to polynomial factors) and in polynomial space.
This result improves the previous bound of $2.8805n$,
which is due to Bj\''orklund and Husfeldt.
To prove our result, we combine an algorithm by Fomin et al.
with Yamamoto's algorithm for the satisfiability problem. In addition,
we show that the 3-domatic number problem can be solved
for graphs $G$ with bounded maximum degree $\Delta (G)$
by a randomized polynomial-space algorithm,
whose running time is better than the previous bound
due to Riege and Rothe whenever $\Delta(G) \geq 5$.
Our new randomized algorithm employs Sch\''oning's approach
to constraint satisfaction problems.
-
id=2006-43
-
-
id=2006-44
- We analyze a list heuristic for the vertex cover problem that
handles the vertices in a given static order based on the degree
sequence. We prove an approximation ratio of at most $\sqrt{\Delta}/2
+3/2$ for a non-increasing degree sequence, and show that no ordering
can achieve an approximation ratio of less than $\sqrt{\Delta}/2$.
-
id=2006-47
- 安定結婚問題の例題は$N$人の男性,$N$人の女性,そして各個人が持つ希
望リストからなる.希望リストは異性全員を含む全順序である.男女間のマッチ
ング$M$において,男性$m$が現在のパートナーよりも女性$w$を好み,$w$が現在
のパートナーよりも$m$を好んでいる時,$m$と$w$をblocking pairと呼ぶ.
blocking pairの無いマッチングを安定マッチングという.与えられた例題から
安定マッチングを求める問題を,安定結婚問題という.GaleとShapleyはどのよ
うな例題にも少なくとも一つは安定マッチングが存在し,その一つを多項式時間
で求めることが出来ることを示した.このような安定結婚問題において,同順位
リストと不完全リストの存在を許した問題に対して最大サイズの安定マッチング
を見つける問題を考える.この問題はNP困難であり,現在知られている中で最も
良い近似アルゴリズムは,($2-c\frac{1}{\sqrt{N}}$)-近似アルゴリズムである.
(ここで,$c$は$c\le \frac{1}{4\sqrt{6}}$を満たす正定数である.)本研究
では,この近似度を$1.8$に改良し,その解析が厳密であることを示した.$2$よ
りも厳密に良い近似度を持つ結果としては,本研究が初めての結果となる.