岩間研究室 発表論文
2008年度
[ 論文誌 ]
- 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点連結性の検査'',
- 電子情報通信学会コンピューテーション研究会, 信学技報, vol.108, no.89, pp.49--55, 2008年 6月.
-
-
>> Abstract
- id=2008-25
- N. Kinosita, S. Tamaki, K. Iwama,
- ``An Improvement of the Soundness of a 3-bit PCP'',
- 冬のLAシンポジウム, pp.19.1--19.8, 2009年 1月.
-
-
>> Abstract
- id=2008-26
- 濱田浩気, 宮崎修一, 岩間一雄,
- ``配属人数下限付き研修医配属問題'',
- 冬のLAシンポジウム, pp.12.1--12., 2009年 1月.
- id=2008-28
- 岡本和也, 宮崎修一,
- ``オンラインOVSF符号割当問題における競合比の上下限の改良'',
- 電子情報通信学会総合大会講演論文集, pp., 2009年 3月.
-
-
>> Abstract
- id=2008-29
- 吉田悠一, 伊藤大雄,
- ``最大独立集合と最大マッチングに対する定数時間近似アルゴリズム'',
- 電子情報通信学会総合大会講演論文集, pp., 2009年 3月.
[ 解説 ]
- id=2008-05
- 伊藤大雄,
- ``離散数学のすすめ4 フランク・ハラリィの一般化三並べ'',
- 理系への数学, vol.第41巻第4号通巻496号, pp.60--64, 2008年 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よりも良いオンラインアルゴリズムが 存在しないことを示す。