# 岩間研究室 発表論文

## [ 著書 ]

id=2006-25

アルゴリズム・サイエンス: 出口からの超入門,

## [ 論文誌 ]

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'',

>> Abstract
id=2006-08
※ 清成悠貴, 宮野英次, 宮崎修一,
試問予定表作成問題の計算複雑さ'',

>> Abstract
id=2006-20
T. Horiyama, K. Iwama, and K. Seto,
Constant Depth Circuits for Symmetric Boolean Functions'',

>> Abstract
id=2006-23
※ 吉牟田拓朗, 宮野英次, 宮崎修一,
オンラインTSPアルゴリズムに対する下限について'',

>> Abstract
id=2006-24

3彩色不能な平面グラフの構成'',

id=2006-32
※ 朝廣雄一, 宮野英次, 宮崎修一, 吉牟田拓朗,
サイクルグラフ上での地図作成問題に対する重み付き最近傍アルゴリズム'',

>> Abstract
id=2006-33

安定結婚問題に対する1.875-近似アルゴリズム'',

>> Abstract
id=2006-35
H. Morizumi, and J. Tarui,
Linear-Size Log-Depth Negation-Limited Inverter for k-tonic 0/1 Sequences'',

>> Abstract
id=2006-36

Negation-Limited Complexity of Parity and Inverters'',

>> Abstract
id=2006-37

Improvement of the Algorithm for the Traveling Salesman Problem on Cubic Graphs'',

>> Abstract
id=2006-47

安定結婚問題に対する1.8-近似アルゴリズム'',

>> Abstract

## [ 解説 ]

id=2006-01
※ 宮崎修一,
ルータ上のバッファ管理問題に対するオンラインアルゴリズム'',

>> 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

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

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

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

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