# 岩間研究室 発表論文

## [ 論文誌 ]

id=2008-15
K. Iwama, S. Miyazaki, and N. Yamauchi,
A (2-c 1 /$\sqrt{N}$)-Approximation Algorithm for the Stable Marriage Problem'',
Algorithmica, vol.51, no.3, pp.342--356, Jul. 2008.

>> Abstract
id=2008-16
X. Han, K. Iwama, and G. Zhang,
Online Removable Square Packing'',
Theory of Computing Systems, vol.43, no.1, pp.38--55, Aug. 2008.

>> Abstract
id=2008-18
W. Bein, K. Iwama, and J. Kawahara,
Randomized Competitive Analysis for Two Server Problems'',
Algorithms, vol.1, pp.30--42, Sep. 2008.

>> Abstract
id=2008-19
Y. Hanatani, T. Horiyama, K. Iwama, and S. Tamaki,
New Graph Calculi for Planar Non-3-Colorable Graphs'',
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol.E91-A, no.9, pp.2301--2307, Sep. 2008.

>> Abstract
id=2008-20
H. Fujiwara, K. Iwama, and K. Yonezawa,
Online chasing problems for regular polygons'',
Information Processing Letters, vol.108, no.3, pp.155--159, Oct. 2008.

>> Abstract
id=2008-21
K. Iwama, H. Morizumi, and J. Tarui,
Reductions for monotone Boolean circuits'',
Theoretical Computer Science, vol.408, 2-3, pp.208--212, Nov. 2008.

>> Abstract
id=2008-24
E..M. Arkin, S.W. Bae, A. Efrat, K. Okamoto, J.S.B. Mitchel, and V. Polishchuk,
Geometric stable roommates'',
Information Processing Letters, vol.109, no.4, pp.219--224, Jan. 2009.

>> Abstract
id=2008-27
Kazuo Iwama, Eiji Miyano, and Hirotaka Ono,
Drawing Borders Efficiently'',
Theory of Computing Systems, vol.44, no.2, pp.230--244, Feb. 2009.

## [ 国際会議 ]

id=2008-01
K. Iwama, S. Miyazaki, and K. Okamoto,
Inapproximability of Stable Roommates Problem with Triple Rooms'',
Proc. 1st Asian Association for Algorithms and Computation (AAAC), pp.30, Apr. 2008.
id=2008-02
M. Yamamoto, and O. Watanabe,
Belief Propagation and Spectral Method'',
Proc. 1st Asian Association for Algorithms and Computation (AAAC), pp.47, Apr. 2008.
id=2008-03
Y. Yoshida, and H. Ito,
On $k$-Connectivity Testing in Degree-Bounded Graphs'',
Proc. 1st Asian Association for Algorithms and Computation (AAAC), pp.56, Apr. 2008.
id=2008-04
K. Iwama, and S. Tamaki,
The Complexity of the Hajos Calculus for Planar Graphs'',
Proc. 1st Asian Association for Algorithms and Computation (AAAC), pp.65, Apr. 2008.
id=2008-06
K. Iwama,
SAT, UNSAT and Coloring'',
Proc. 11th International Symposium on the Theory and Applications of Satisfiability Testing (SAT 2008), LNCS 4996, pp.153, May 2008.
id=2008-09
H. Fujiwara, K. Iwama, and Y. Sekiguchi,
Average-Case Competitive Analyses for One-Way Trading'',
Proc. the 14th Annual International Computing and Combinatorics Conference (COCOON 2008), LNCS 5092, pp.41--51, Jun. 2008.

>> Abstract
id=2008-10
K. Okamoto, W. Chen, and X. Y. Li,
Ranking of Closeness Centrality for Large-Scale Social Networks'',
Proc. the Second International Frontiers of Algorithmics Workshop (FAW 2008), LNCS 5059, pp.186--195, Jun. 2008.

>> Abstract
id=2008-12
K. Hamada, K. Iwama, and S. Miyazaki,
The Hospitals/Residents Problem with Quota Lower Bounds'',
MATCH-UP (Satellite workshop of ICALP 2008), pp.55--66, Jul. 2008.

>> Abstract
id=2008-13
K. Iwama, H. Nishimura, M. Paterson, R. Raymond, and S. Yamashita,
Polynomial-Time Construction of Linear Network Coding'',
Proc. 35th International Colloquium on Automata, Languages and Programming (ICALP 2008), LNCS 5125, pp.271--282, Jul. 2008.

>> Abstract
id=2008-14
Y. Yoshida, and H. Ito,
Property Testing on $k$-Vertex-Connectivity of Graphs'',
Proc. 35th International Colloquium on Automata, Languages and Programming (ICALP 2008), LNCS 5125, pp.539-550, Jul. 2008.

>> Abstract
id=2008-17
W. Bein, K. Iwama, and J. Kawahara,
Randomized Competitive Analysis for Two-Server Problems'',
Proc. 16th Annual European Symposium on Algorithms (ESA 2008), LNCS 5193, pp.161--172, Sep. 2008.

>> Abstract
id=2008-22
S. Miyazaki, and K. Okamoto,
Improving the Competitive Ratio of the Online OVSF Code Assignment Problem'',
Proc. the 19th International Symposium on Algorithms and Computation (ISAAC 2008), LNCS 5369, pp.64-76, Dec. 2008.

>> Abstract
id=2008-23
A. Ambainis, K. Iwama, M. Nakanishi, H. Nisimura, R. Raymond, S. Tani, and S. Yamashita,
Quantum Query Complexity of Boolean Functions with Small On-Sets'',
Proc. the 19th International Symposium on Algorithms and Computation (ISAAC 2008), LNCS 5369, pp.907-918, Dec. 2008.

>> Abstract

## [ 国内発表 ]

id=2008-11

無向グラフのk点連結性の検査'',

>> Abstract
id=2008-25
N. Kinosita, S. Tamaki, K. Iwama,
An Improvement of the Soundness of a 3-bit PCP'',

>> Abstract
id=2008-26

配属人数下限付き研修医配属問題'',

id=2008-28

オンラインOVSF符号割当問題における競合比の上下限の改良'',

>> Abstract
id=2008-29

最大独立集合と最大マッチングに対する定数時間近似アルゴリズム'',

## [ 解説 ]

id=2008-05

離散数学のすすめ4 フランク・ハラリィの一般化三並べ'',

id=2008-07
K. Iwama,
Local Search Algorithms for kSAT'',
Encyclopedia of Algorithms, SpringerEncyclopedia of Algorithms, Springer, pp.468--470, Jun. 2008.
id=2008-08
K. Iwama, and S. Miyazaki,
Stable Marriage with Ties and Incomplete Lists'',
Encyclopedia of Algorithms, SpringerEncyclopedia of Algorithms, Springer, pp.883--885, Jun. 2008.

## Abstract

id=2008-09
Consider a trader who exchanges one dollar into yen and assume that the exchange rate fluctuates within the interval $[m,M]$. The game ends without advance notice, then the trader is forced to exchange all the remaining dollars at the minimum rate $m$. El-Yaniv et al presented the optimal worst-case threat-based strategy (WTB) for this game [4].In this paper, under the assumption that the distribution of the maximum exchange rate is known, we provide average-case analyses using all the reasonable optimization measures and derive different optimal algorithms for each of them. Remarkable differences in behavior are as follows: Unlike other algorithms, the average-case threat-based strategy (ATB) that minimizes $E[OPT/ALG]$ exchanges little by little. The maximization of $E[ALG/OPT]$ and the minimization of $E[OPT]/E[ALG]$lead to similar algorithms in that both exchange all at once. However, their timing is different.
id=2008-10
Closeness centrality is an important concept in social network analysis. In a graph representing a social network, closeness centrality measures how close a vertex is to all other vertices in the graph. In this paper, we combine existing methods on calculating exact values and approximate values of closeness centrality and present new algorithms to rank the top-k vertices with the highest closeness centrality. We show that under certain conditions, our algorithm is more efficient than the algorithm that calculates the closeness-centralities of all vertices. Closeness centrality is an important concept in social network analysis. In a graph representing a social network, closeness centrality measures how close a vertex is to all other vertices in the graph. In this paper, we combine existing methods on calculating exact values and approximate values of closeness centrality and present new algorithms to rank the top-k vertices with the highest closeness centrality. We show that under certain conditions, our algorithm is more efficient than the algorithm that calculates the closeness-centralities of all vertices.
id=2008-11
We present an algorithm for testing $k$-vertex-connectivity of graphs with given maximum degree. The time complexity of the algorithm is independent to the number of vertices and edges of graphs. It is the first constant-time $k$-vertex-connectivity testing algorithm for general $k\geq 4$. A graph $G$ with $n$ vertices and maximum degree at most $d$ is called $\epsilon$-far from $k$- vertex-connectivity when at least $\frac{\epsilon dn}{2}$ edges must be added to or removed from $G$ to obtain a $k$-vertex-connected graph with maximum degree at most $d$. The algorithm always accepts every graph which is $k$-vertex-connected and rejects every graph which is $\epsilon$-far from $k$-vertex-connectivity with probability at least $2/3$.
id=2008-12
The Hospitals/Residents problem (HR for short) is a many-to-one extension of the stable marriage problem. In an instance of HR, each hospital specifies a quota, i.e., an upper bound on the number of positions it provides, and a feasible matching must satisfy the condition that the number of residents assigned to each hospital is up to its quota. It is well-known that in any instance, there exists at least one stable matching, and finding one can be done in polynomial time. In this paper, we consider an extension where each hospital specifies upper and {\em lower} bounds on its number of positions, namely, in a feasible matching, the number of residents assigned to each hospital is at most its upper bound quota and at least its lower bound quota. Now, some instance admits no stable matching, but it is easy to see that the problem of asking if there is a stable matching is solved in polynomial time. We consider an optimization version of this problem, that is, the problem of finding a feasible solution with minimum number of blocking pairs. We show that it is hard to approximate within $(|H|+|R|)^{1-\varepsilon}$ for any positive constant $\varepsilon$, where $H$ and $R$ are the sets of hospitals and residents, respectively. This inapproximability result holds even if all preference lists are complete and strict, and all hospitals have the same preference list (known as the master list''). We further consider the restriction that, in addition to the above, all residents have the same preference list, and show that this can be solved in polynomial time.
id=2008-13
Constructing $k$ independent sessions between $k$ source-sink pairs with the help of a linear operation at each vertex is one of the most standard problems in network coding. For an unbounded $k$, this is known to be NP-hard. Very recently, a polynomial-time algorithm was given for $k = 2$ [Wang and Shroff, ISIT 2007], but was open for a general (constant) $k$. This paper gives a polynomial-time algorithm for this problem under the assumption that the size of the finite field for the linear operations is bounded by a fixed constant.
id=2008-14
We present an algorithm for testing the $k$-vertex-connectivity of graphs with given maximum degree. The time complexity of the algorithm is independent of the number of vertices and edges of graphs. A graph $G$ with $n$ vertices and maximum degree at most d is called $\epsilon$-far from $k$-vertex-connectivity when at least $\frac{\epsilon dn}{2} edges must be added to or removed from$G$to obtain a$k$-vertex-connected graph with maximum degree at most$d$. The algorithm always accepts every graph that is$k$-vertex-connected and rejects every graph that is$\epsilon$- far from$k$-vertex-connectivity with a probability of at least$2/3$. The algorithm runs in$O(d (\frac{c}{\epsilon d})^k\log\frac{1}{\epsilon d}) time ($c > 1$ is a constant) for given ($k-1$)-vertex- connected graphs, and $O(d(\frac{c}{\epsilon d})^k\log\frac{1}{\epsilon d}) time ($c > 1$is a constant) for given general graphs. It is the first constant-time$k$-vertex-connectivity testing algorithm for general$k \geq 4$. id=2008-15 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 NP-hard and the current best known approximation algorithm achieves the approximation ratio$2-c\frac{\log N}{N}$, where$c$is an arbitrary positive constant and$N$is the number of men in an input. In this paper, we improve the ratio to$2-c\frac{1}{\sqrt{N}}$, where$c$is an arbitrary constant that satisfies$c \leq \frac{1}{4 \sqrt{6}}$. id=2008-16 The online removable square packing problem is a two-dimen-sional version of the online removable Knapsack problem. For a sequence of squares with side length at most 1, we are requested to pack a subset of them into a unit square bin in an online fashion where the online player can decide whether to take the current square or not and which squares currently in the unit square to remove. The goal is to maximize the total packed area. Our results include: (i) No online algorithm can achieve a better competitive ratio than$(\sqrt{5} +3)/2 \approx 2.618. (ii) The matching upper bound is achieved by a relatively simple online algorithm if repacking is allowed. (iii) Without repacking, we can achieve an upper bound of 3 by using the concept of bricks of Januszewski and Lassak. (iv) The offline version of the problem admits a PTAS.
id=2008-17
We prove that there exists a randomized online algorithm for the 2-server 3-point problem whose expected competitive ratio is at most 1.5949. This is the first nontrivial upper bound for randomized $k$-server algorithms in a general metric space whose competitive ratio is well below the corresponding deterministic lower bound (= 2 in the 2-server case).
id=2008-18
We prove that there exists a randomized online algorithm for the 2-server 3-point problem whose expected competitive ratio is at most 1.5897. This is the first nontrivial upper bound for randomized $k$-server algorithms in a general metric space whose competitive ratio is well below the corresponding deterministic lower bound (= 2 in the 2-server case).
id=2008-19
The Haj\'os calculus is a nondeterministic procedure which generates the class of non-3-colorable graphs. If all non-3-colorable graphs can be constructed in polynomial steps by the calculus, then NP~$=$~co-NP holds. Up to date, however, it remains open whether there exists a family of graphs that cannot be generated in polynomial steps. To attack this problem, we propose two graph calculi \phc\ and \phcs\ that generate non-3-colorable planar graphs, where intermediate graphs in the calculi are also restricted to be planar. Then we prove that \phc\ and \phcs\ are sound and complete. We also show that \phcs\ can polynomially simulate \phc.
id=2008-20
We consider a server location problem with only one server to move. In this paper we assume that a request is given as a region and that the service can be done anywhere inside the region. Namely, for each request an online algorithm chooses an arbitrary point in the region and moves the server there. Note that if every request is a single point and the server must exactly go there in the given order as conventional server problems, there is no choice for the online player and the problem is trivial. Our main result shows that if the region is a regular $n$-gon, the competitive ratio of the greedy algorithm is $1/\sin\frac{\pi}{2n}$ for odd $n$, and $1/\sin\frac{\pi}{n}$ for even $n$. In particular for a square region, the greedy algorithm turns out to be optimal.
id=2008-21
The large class, say $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., they have circuits with $O(n\logn )$ AND/OR gates of fan-in two. Suppose that we can use, besides such normal AND/OR gates, any number of more powerful EF$-gatesEwhich 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=2008-22 Online OVSF code assignment has an important application to wireless communications. Recently, this problem was formally modeled as an online problem, and performances of online algorithms have been analyzed by the competitive analysis. The previous best upper and lower bounds on the competitive ratio were 10 and 5/3, respectively. In this paper, we improve them to 7 and 2, respectively. We also show that our analysis for the upper bound is tight by giving an input sequence for which the competitive ratio of our algorithm is 7-$\epsilon$for arbitrary$\epsilon > 0$. id=2008-23 The main objective of this paper is to show that the quantum query complexity$Q(f)$of an$N$-bit Boolean function$f$is bounded by a function of a simple and natural parameter, i.e.,$M = |{x|f(x) = 1}|$or the size of$f'$s on-set. We prove that: (i) For for$poly(N) \leq M \leq 2^{N^d} some constant $0 < d < 1$, the upper bound of $Q(f)$ is $O(\sqrt{N\log M / \log N})$. This bound is tight, namely there is a Boolean function f such that $Q(f)=\Omega (\sqrt{N\log M / \log N})$. (ii) For the same range of $M$, the (also tight) lower bound of $Q(f)$ is $\Omega (\sqrt{N})$. (iii) The average value of $Q(f)$ is bounded from above and below by $Q(f) = O(\log M +\sqrt{N})$ and $Q(f) = \Omega (\log M / \log N +sqrt{N}), respectively. The first bound gives a simple way of bounding the quantum query complexity of testing some graph properties. In particular, it is proved that the quantum query complexity of planarity testing for a graph with n vertices is$\Theta (N^ {3/4}) where $N=\frac{n(n-1)}{2}. id=2008-24 We consider instances of the Stable Roommates problem that arise from geometric representation of participants' preferences: a participant is a point in a metric space, and his preference list is given by the sorted list of distances to the other participants. We show that contrary to the general case, the problem admits a polynomial-time solution even in the case when ties are present in the preference lists. We define the notion of an$\alpha$-stable matching: the participants are willing to switch partners only for a (multiplicative) improvement of at least$\alpha$. We prove that, in general, finding$\alpha$-stable matchings is not easier than finding matchings that are stable in the usual sense. We show that, unlike in the general case, in a three-dimensional geometric stable roommates problem, a 2-stable matching can be found in polynomial time. id=2008-25 Approximation algorithms have been studied to cope with computationally hard combinatorial problems such as NP-hard problems, for which we cannot hope for exact solutions efficiently. Approximation algorithms compute feasible solutions with some theoretically guaranteed quality in polynomial time. Probabilistically Checkable Proofs (PCPs) have been succeeded to show the limitation of such approximation algorithms, that is, how good approximate solutions can be compared to optimal solution. PCP is a mathematical model which probabilistically recognizes a certain (especially NP) language$L$by making queries to a kind of oracle called a proof. There are some important parameters which characterize PCPs. Completeness (soundness) is the maximum probability that a PCP accepts an input which is in (respectively, not in)$L$. The number of queries to the proof and the adaptivity in queries, that means a dependency between the queries, are also important aspects. In this paper, we study how small the soundness of a PCP can be when it has perfect completeness and makes non-adaptive three queries. We can show better hardness of approximation of the optimization problem corresponding to a PCP if we can construct a PCP with smaller soundness. Khot and Saket obtained a PCP with soundness value$\frac{20}{27}+\epsilon\simeq 0.74074$, that probabilistically selects one of four tests and perform it to the proof. We show that the soundness can be$\frac{16+\sqrt{6}}{25}+\epsilon\simeq 0.73798$by optimizing the probability of selecting each test. Here$\epsilon\$ is an arbitrarily small constant. As a result of our optimization, one of the four tests are shown to be unnecessary.
id=2008-28
オンラインOVSF符号割当問題は第3世代携帯電話(3G)技術に応用される重要な問 題である。オンラインOVSF符号割当問題はオンライン問題としてモデル化されて おり、オンラインOVSF符号割当問題に対するオンラインアルゴリズムの性能が競 合比によって評価されてきた。そして、これまでに知られていたオンラインアル ゴリズムの中で、最も良い性能を持つアルゴリズムの競合比は10であった。ま た、競合比の下限として、競合比が5/3よりも良いオンラインアルゴリズムが存 在しないことが示されていた。我々は新しいオンラインアルゴリズムを開発し、 そのアルゴリズムの競合比が7となることを示し、さらに、我々の解析が厳密な ものであることを示す。また、競合比が2よりも良いオンラインアルゴリズムが 存在しないことを示す。