岩間研究室発表論文

2007年度

[ 論文誌 ]

id=2007-07: H. Ito, M. Kobayashi, and G. Nakamura,; ``Semi-Distance Codes and Steiner Systems'',; Akiyama-Chv\'atal Festschrift, Supplement of Graphs and Combinatorics, vol.23, pp.283--290, Jun. 2007.

id=2007-08: H. Ito, G. Nakamura, and S. Takata,; ``Winning Ways of Weighted Poset Games'',; Akiyama-Chv\'atal Festschrift, Supplement of Graphs and Combinatorics, vol.23, pp.291--306, Jun. 2007.; >> Abstract

id=2007-15: A. Ambainis, K. Iwama, A. Kawachi, R. Raymond, and S. Yamashita,; ``Improved Algorithms for Quantum Identification of Boolean Oracles'',; Theoretical Computer Science, vol.378, no.1, pp.41--53, Jun. 2007.

id=2007-18: K. Iwama, and S. Tamaki,; ``Exploiting Partial Knowledge of Satisfying Assignments'',; Discrete Applied Mathematics, vol.155, no.12, pp.1596--1603, Jun. 2007.; >> Abstract

id=2007-27: M. M. Halldorsson, K. Iwama, S. Miyazaki, and H. Yanagisawa,; ``Improved Approximation Results for the Stable Marriage Problem'',; ACM Transactions on Algorithms, vol.3, 3/30, Aug. 2007.; >> Abstract

[ 国際会議 ]

id=2007-01: T. Horiyama, K. Iwama, and D. Sumita,; ``Truthful Auctions with Limited Range of Bids'',; Proc. of the 5th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, pp.53--61, Apr. 2007.; >> Abstract

id=2007-02: W. Bein, J. Correa, and X. Han,; ``A Fast Asymptotic Approximation Scheme for Bin Packing with Rejection'',; Proc. the First International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies (ESCAPE 2007), LNCS 4614, Apr. 2007.; >> Abstract

id=2007-04: K. Makino, S. Tamaki, and M. Yamamoto,; ``On the Boolean Connectivity Problem for Horn Relations'',; Proc. 10th International Conference on Theory and Applications of Satisfiability Testing (SAT), LNCS 4501, pp.187--200, May 2007.; >> Abstract

id=2007-05: H. Morizumi, and J. Tarui,; ``Linear-Size Log-Depth Negation-Limited Inverter for k-tonic Binary Sequences'',; Proc. of the 4th Annual Conference on Theory and Applications of Models of Computation (TAMC 2007), LNCS 4484, pp.605--615, May 2007.; >> Abstract

id=2007-09: X. Han, K. Iwama, D. Ye, and G. Zhang,; ``Strip Packing vs. Bin Packing'',; The Third International Conference on Algorithmic Aspects in Information and Management (AAIM 2007), LNCS 4508, Jun. 2007.; >> Abstract

id=2007-10: K. Iwama, E. Miyano, and H. Ono,; ``Drawing Borders Efficiently'',; Proc. 4th International Conference on Fun with Algorithms (FUN 2007), LNCS 4475, pp.213--226, Jun. 2007.

id=2007-11: S. Bereg, and H. Ito,; ``Transformating Graphs with the Same Graphic Sequences'',; Kyoto International Conference on Computational Geometry and Graph theory --- in honor of Jin Akiyama and Va$\check{\mbox{s}}$ek Chv\'atal on their 60th birthdays (KyotoCGGT2007), Jun. 2007.

id=2007-12: H. Ito, G. Nakamura, and S. Takata,; ``Winning Ways of Weighted Poset Games'',; Kyoto International Conference on Computational Geometry and Graph theory --- in honor of Jin Akiyama and Va$\check{\mbox{s}}$ek Chv\'atal on their 60th birthdays (KyotoCGGT2007), Jun. 2007.

id=2007-16: ※ K. Kobayashi, S. Miyazaki, and Y. Okabe,; ``A Tight Bound on Online Buffer Management for Two-port Shared-Memory Switches'',; Proc. 19th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2007), pp.358--364, Jun. 2007.; >> Abstract

id=2007-19: K. Iwama, and T. Nakashima,; ``An Improved Exact Algorithm for Cubic Graph TSP'',; Proc. the 13th Annual International Computing and Combinatorics Conference (COCOON 2007), LNCS 4598, pp.108--117, Jul. 2007.; >> Abstract

id=2007-20: X. Deng, K. Iwama, Q. Qi, A. W. Sun, and T. Tasaka,; ``Properties of Symmetric Incentive Compatible Auctions'',; Proc. the 13th Annual International Computing and Combinatorics Conference (COCOON 2007), LNCS 4598, pp.264--273, Jul. 2007.; >> Abstract

id=2007-21: K. Iwama, H. Nishimura, R. Raymond, and S. Yamashita,; ``Unbounded-Error One-Way Classical and Quantum Communication Complexity'',; Proc. 34th International Colloquium on Automata, Languages and Programming (ICALP 2007), LNCS 4596, Jul. 2007.

id=2007-25: K. Iwama, S. Miyazaki, and K. Okamoto,; ``Stable Roommates Problem with Triple Rooms'',; Proc. the 10th Japan-Korea Joint Workshop on Algorithms and Computation (WAAC 2007), pp.105--112, Aug. 2007.; >> Abstract

id=2007-26: K. Iwama, S. Miyazaki, and H. Yanagisawa,; ``Approximation Algorithms for the Sex-Equal Stable Marriage Problem'',; Proc. 10th Workshop on Algorithms and Data Structures (WADS 2007), LNCS 4619, pp.201--213, Aug. 2007.; >> Abstract

id=2007-28: K. Iwama, and G. Zhang,; ``Optimal Resource Augmentations for Online Knapsack'',; Proc. 10th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2007), Aug. 2007.

id=2007-34: H. Ito, and H. Miyagawa,; ``Snaky is a Winner with One Handicap'',; Proc. 8th Hellenic European Conference on Computer Mathematics and its Applications (HERCMA 2007), pp.25--26, Sep. 2007.; >> Abstract

id=2007-35: W. Bein, K. Iwama, J. Kawahara, L. Larmore, and J. Oravec,; ``A Randomized Algorithm for Two Servers in Cross Polytope Spaces'',; Proc. 5th Workshop on Approximation and Online Algorithms (WAOA 2007), LNCS 4927, pp.246--259, Oct. 2007.; >> Abstract

id=2007-36: K. Kobayashi, and K. Okamoto,; ``Improved Upper Bounds on the Competitive Ratio for Online Realtime Scheduling'',; Proc. the 15th Annual European Symposium on Algorithms (ESA 2007), LNCS 4698, pp.463--474, Oct. 2007.; >> Abstract

id=2007-40: M. Yamamoto,; ``A Spectral Method for MAX2SAT in the Planted Solution Model'',; Proc. the 18th International Symposium on Algorithms and Computation (ISAAC 2007), LNCS 4835, pp.112--123, Dec. 2007.; >> Abstract

id=2007-41: K. Iwama, H. Nishimura, R. Raymond, and S. Yamashita,; ``Unbounded-error classical and quantum communication complexity'',; Proc. the 18th International Symposium on Algorithms and Computation (ISAAC 2007), LNCS 4835, pp.100 -- 111, Dec. 2007.

id=2007-44: H. Ito, M. Paterson, and K. Sugihara,; ``Multi-Commodity Source Location Problems and Price of Greed'',; Proc. the 2nd Workshop in Algorithms and Computation (WALCOM 2008), LNCS 4921, Feb. 2008.; >> Abstract

[ 国内発表 ]

id=2007-13: 宮川博光, 伊藤大雄, 岩間一雄,; ``部の大きさの比が高々定数倍の孤立２部クリークの列挙'',; 電子情報通信学会コンピュテーション研究会, 信学技報, vol.107, no.127, COMP2007-19, pp.9--16, 2007年 6月.; >> Abstract

id=2007-14: 吉田悠一, 伊藤大雄,; ``有向グラフにおける$k$枝連結性の検査'',; 電子情報通信学会コンピュテーション研究会, 信学技報, vol.107, no.127, COMP2007-20, pp.17--23, 2007年 6月.; >> Abstract

id=2007-17: ※ 小林浩二, 宮崎修一, 岡部寿男,; ``A Tight Upper Bound on Online Buffer Management for Two-port Shared-Memory Switches'',; 電子情報通信学会コンピュテーション研究会, 信学技報, vol.107, no.127, COMP2007-26, pp.63--70, 2007年 6月.; >> Abstract

id=2007-22: M. Yamamoto,; ``A Spectral Method for MAX2SAT in the Planted Solution Model'',; 夏のLAシンポジウム, pp.6.1--6.2, Jul. 2007.

id=2007-23: Y. Hanatani, T. Horiyama, K. Iwama, and S. Tamaki,; ``The Complexity of the Haj\'os Calculus on Planar Graphs'',; 夏のLAシンポジウム, pp.8.1--8.20, Jul. 2007.; >> Abstract

id=2007-24: ※ 森本尚之, 宮崎修一, 岡部寿男,; ``サイクルグラフ上での地図作成問題に対する最適なオンラインアルゴリズム'',; 夏のLAシンポジウム, pp.9.1--9.11, 2007年 7月.; >> Abstract

id=2007-30: ※清成悠貴, 宮野英次, 宮崎修一,; ``試問予定表作成問題の制約付きモデルに対するNP困難性'',; 平成19年度第60回電気関係学会九州支部連合大会, vol.09-1A-04, pp.87, 2007年 9月.

id=2007-31: H. Ito, M. Paterson, K. Sugihara,; ``Multi-Commodity Source Location Problems and Price of Greed'',; 情報科学技術フォーラム;FIT, pp., 2007年 9月.

id=2007-32: Y. Hanatani, T. Horiyama, K. Iwama, and S. Tamaki,; ``The Complexity of the Haj\'os Calculus on Planar Graphs'',; 電子情報通信学会コンピュテーション研究会, 信学技報, vol.107, no.219, COMP2007-38, pp.43--50, Sep. 2007.

id=2007-33: ※ 森本尚之, 宮崎修一, 岡部寿男,; ``サイクル上でのグラフ探索問題に対する最適なオンラインアルゴリズム'',; 電子情報通信学会コンピュテーション研究会, 信学技報, vol.107, no.219, COMP2007-39, pp.51--57, 2007年 9月.

id=2007-37: 岡本和也, 宮崎修一, 岩間一雄,; ``3人部屋安定ルームメイト問題のNP完全性'',; 電子情報通信学会コンピュテーション研究会, 信学技報, vol.107, no.258, COMP2007-41, pp.1--6, 2007年 10月.; >> Abstract

id=2007-39: 伊藤大雄, 笠原正治,; ``待機電力問題'',; ミニシンポジウム新世代計算限界と地球環境問題, 2007年 12月.

id=2007-42: 市場孝之, 岩間一雄,; ``正直なオークションにおける談合の影響'',; 冬のLAシンポジウム, 京都大学数理解析研究所講究録, pp.38.1--38.8, 2007年 1月.

id=2007-45: 小林浩二, 岡本和也,; ``オンライン実時間スケジューリング問題における\\競合比の上限の改良'',; 電子情報通信学会総合大会講演論文集, 2008年 3月.; >> Abstract

[ 解説 ]

id=2007-03: 伊藤大雄,; ``離散数学のすすめ01 離散数学へのいざない'',; 理系への数学, vol.第40巻第4号通巻484号, pp.8--14, 2007年 4月.

id=2007-06: 伊藤大雄,; ``離散数学のすすめ02 最短路問題'',; 理系への数学, vol.第40巻5号通巻485号, pp.46--51, 2007年 5月.

id=2007-29: ※宮崎修一,; ``離散数学のすすめ06 安定結婚問題'',; 理系への数学, vol.第40巻第9号通巻489号, pp.49--54, 2007年 9月.

id=2007-38: 伊藤大雄,; ``離散数学のすすめ12 ケーキ分割問題'',; 理系への数学, vol.第40巻第12号通巻492号, pp.47--53, 2007年 12月.

id=2007-43: 玉置卓,; ``離散数学のすすめ11 計算量理論の最先端'',; 理系への数学, vol.第41巻第2号通巻494号, pp.49--53, 2008年 2月.

Abstract

id=2007-01: We study single-round and sealed-bid truthful auctions with unlimited supply of goods. In this paper, we propose to analyze the behavior of truthful auctions by introducing a parameter $r$ that indicates the ratio between the minimum and the maximum bid values. By making use of the minimum and the maximum bid values, five truthful auction algorithms are proposed. We can achieve the competitive ratio $\ln r + 1$, which gives better results than the conventional sampling cost sharing auction for small $r$. Lower bound analysis is also given. For the two bidders auction, the competitive ratio is at least $2 - \frac{1}{r}$ for any truthful auctions. Similar bound holds for general case.

id=2007-02: The bin packing with rejection problem is the following: Given a list of items with associated sizes and rejection costs, find a packing into unit bins of a subset of the list such that the number of bins used plus the sum of rejection costs of unpacked items is minimized. In this paper, we first show that bin packing with rejection can be reduced to $n$ multiple knapsack problems. Then, based on techniques for the multiple knapsack problem we give a fast asymptotic polynomial time approximation scheme with time complexity $O(n^{O(\epsilon^{-2})})$. This improves a recent approximation scheme given by Epstein, which has time complexity $O(n^{O((\epsilon^{-4})^{\epsilon^{-1}})})$. Finally, we show that our algorithm can be extended to variable-sized bin packing with rejection and give an asymptotic polynomial time approximation scheme for it.

id=2007-04: Gopalan et al.\ studied in ICALP06 [GKM06] connectivity properties of the solution-space of Boolean formulas, and investigated complexity issues on the connectivity problems in Schaefer's framework. A set $S$ of logical relations is $\schaefer$ if all relations in $S$ are either bijunctive, Horn, dual Horn, or affine. They conjectured that the connectivity problem for $\schaefer$ is in $\P$. We disprove their conjecture by showing that there exists a set $S$ of Horn relations such that the connectivity problem for $S$ is $\coNP$-complete. We also show that the connectivity problem for bijunctive relations can be solved in $O(\min \{n|\gvp|, T(n)\})$ time, where $n$ denotes the number of variables, $\gvp$ denotes the corresponding 2-CNF formula, and $T(n)$ denotes the time needed to compute the transitive closure of a directed graph of $n$ vertices. Furthermore, we investigate a tractable aspect of Horn and dual Horn relations with respect to characteristic sets.

id=2007-05: A zero-one sequence $x_1,\ldots,x_n$ is {\em $k$-tonic\/} if the number of $i$'s such that $x_i \ne x_{i+1}$ is at most~$k$. The notion generalizes well-known {\em bitonic\/} sequences. 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. In this context, the study of {\em inverters\/}, i.e., circuits with inputs $x_1,\ldots,x_n$ and outputs $\neg{x_1},\ldots,\neg{x_n}$, is fundamental since an inverter with $r$ NOTs can be used to convert a general circuit to one with only $r$ NOTs. In particular, if linear-size log-depth inverter with $r$ NOTs exists, we do not lose generality by only considering circuits with at most $r$ NOTs when we seek superlinear size lower bounds or superlogarithmic depth lower bounds. Markov [JACM1958] showed that the minimum number of NOT gates necessary in an $n$-inverter is $\lceil\log_2(n+1)\rceil$. Beals, Nishino, and Tanaka [SICOMP98--STOC95] gave a construction of an $n$-inverter with size $O(n\log n)$, depth $O(\log n)$, and $\lceil\log_2(n+1)\rceil$ NOTs. We give a construction of circuits inverting $k$-tonic sequences with size $O((\log k)\, n)$ and depth $O(\log k\,\log\log n + \log n)$ using $\log_2 n+\log_2\log_2\log_2 n + O(1)$ NOTs. In particular, for the case where $k=O(1)$, our $k$-tonic inverter achieves asymptotically optimal linear size and logarithmic depth. Our construction improves all the parameters of the $k$-tonic inverter by Sato, Amano, and Maruoka~[COCOON06] with size $O(kn)$, depth $O(k\log2 n)$, and $O(k\log n)$ NOTs. We also give a construction of $k$-tonic {\em sorters\/} achieving linear size and logarithmic depth with $\log_2\log_2 n + \log_2\log_2\log_2 n + O(1)$ NOT gates for the case where $k=O(1)$. The following question by Tur\'{a}n remains open: Is the size of any depth-$O(\log n)$ inverter with $O(\log n)$ NOT gates superlinear?

id=2007-08: In this paper, we introduce the {\it weighted poset game}, which is defined as an extension of the poset (partially-ordered set) game by adding a weight on every element of the poset. Each player has their own non-negative number of lives, and loses as many lives as the sum of the element weights they took. The player whose lives become negative first is the loser. We consider winning ways of this problem. First, for the problem with $\{ 0,1 \}$-weights, we find that (1) if the number of lives are different, then the player who has the large number of lives is the winner, (2) if the number of lives are the same and all maximal elements have positive weights, then the second player is a winner, and (3) otherwise, the game is reduced to an (unweighted) poset game. Next, for general weights, we consider the case where the partial order is a total order, and derive a polynomial-time algorithm for calculating who is the winner and the winning way for the winner.

id=2007-09: In this paper we establish a general algorithmic framework between bin packing and strip packing, with which we achieve the same asymptotic bounds by applying bin packing algorithms to strip packing. More precisely we obtain the following results: (1) Any offline bin packing algorithm can be applied to strip packing maintaining the same asymptotic worst-case ratio. Thus using FFD (First Fit Decreasing Height) as a subroutine, we get a practical (simple and fast) algorithm for strip packing with an upper bound 11/9. (2) A class of Harmonic-based algorithms for bin packing can be applied to online strip packing maintaining the same asymptotic competitive ratio. It implies online strip packing admits an upper bound of 1.58889 on the asymptotic competitive ratio. This significantly improves the previously best bound of 1.6910 and affirmatively answers an open question.

id=2007-13: グラフ$G=(V,E)$の最大の2部クリークを求める問題や極大の2部クリークを列挙する問題は難しい．クリークでも同様に難しいが，極大孤立クリークの列挙は線形時間ですべて列挙できることが分かっている．本稿では極大孤立2部クリークを列挙する問題を扱う．しかし，極大孤立2部クリークは指数個存在する場合があることが示せるので，二つの部の大きさの比が定数である様な極大孤立2部クリークについて扱う．それらが線形個しか存在しないことを示し，それらをすべて列挙する線形時間アルゴリズムを提案する．

id=2007-14: 本報告では、次数に上限のある有向グラフが$k$枝連結であるか、または$k$枝連結から$\epsilon$遠隔であるかを検査する、グラフの頂点と枝の数によらない定数時間アルゴリズムを示す。頂点数$n$、次数の上限$d$の有向グラフ$G$が$k$枝連結から$\epsilon$遠隔であるとは、次数の上限を保ったまま$G$を$k$枝連結にするのに、少なくとも$\epsilon dn$本の辺の追加及び削除が必要であることを言う。本報告で示す検査アルゴリズムは、性質検査（Property Testing）と呼ばれる概念に基づいている。これは入力グラフが$k$枝連結であれば$2/3$以上の確率で受理し、$k$枝連結から$\epsilon$遠隔であれば$2/3$以上の確率で拒否するものとして定義される。どちらでもないグラフに対しては、何を出力してもかまわない。我々は、$k$-1枝連結なグラフに対して$O\left(d\left(\frac{c}{\epsilond}\right)^{k}\log\frac{1}{\epsilon d}\right)$$($$c>1$は定数$)$時間、一般のグラフに対して$O\left(d\left(\frac{ck}{\epsilon d}\right)^{k}\log\frac{k}{\epsilon d}\right)$$($$c>1$は定数$)$時間の検査アルゴリズムを得た。

id=2007-16: The online buffer management problem formulates the problem of queueing policies of network switches supporting QoS (Quality of Service) guarantee. For this problem, several models are considered. In this paper, we focus on shared memory switches with preemption. We prove that the competitive ratio of the Longest Queue Drop ($LQD$) policy is $\frac{4M-4}{3M-2}$ in the case of $N=2$, where $N$ is the number of output ports in a switch and $M$ is the size of the buffer. This matches the lower bound given by Hahne, Kesselman and Mansour. Also, in the case of arbitrary $N$, we improve the competitive ratio of $LQD$ from $2$ to $2 - \frac{1}{M} \min_{K = 1, 2, ..., N}\{ \lfloor \frac{M}{K} \rfloor + K - 1\}$.

id=2007-17: オンラインバッファ管理問題は, 近年のネットワーク運用における主要な論点となっているQoS (Quality of Service)保証実現のための, スイッチなどのキュー管理をオンライン問題として定式化した問題であり, 様々なモデルが考案されている.本論文ではその中の1つである共有メモリ型スイッチを扱ったモデルを取り上げる.我々は, スイッチの出力ポートの数Nが2であるときに、アルゴリズムLongest Queue Policy (LQD)の競合比が$\frac{4M-4}{3M-2}$ であることを示した。ここで, Mはスイッチのバッファのサイズである.これは、Hahneらによって示された下限に一致する. また、任意のNの場合に、LQDの競合比を$2$から$2 - \frac{1}{M} \min_{K = 1, 2, ..., N}\{ \lfloor \frac{M}{K} \rfloor + K - 1\}$に改良した.

id=2007-18: Recently Schoning has shown that a simple local-search algorithm for 3SAT achieves the currently best upper bound, i.e., an expected time of $1.334^n$. In this paper, we show that this algorithm can be modified to run much faster if there is some kind of imbalance in satisfying assignments and we have a (partial) knowledge about that. Especially if a satisfying assignment has imbalanced 0's and 1's, i.e., $p_1 n$ 1's and $(1-p_1)n$ 0's, then we can find a solution in time $1.260^n$ when $p_1=1/3$ and $1.072^n$ when $p_1=0.1$. Such an imbalance often exists in SAT instances reduced from other problems. As a concrete example, we investigate a reduction from 3DM and show our new approach is nontrivially faster than its direct algorithms. Preliminary experimental results are also given.

id=2007-19: It is shown that the traveling salesman problem for graphs of degree at most three with $n$ vertices can be solved in time $O(1.251^{n})$, improving the previous bound $O(1.260^n)$ by Eppstein.

id=2007-20: We formalize the definition of symmetric auctions to study fundamental properties of incentive compatible auction protocols. We characterize such auction protocols for those with a fixed number of items to sell and study some important properties of those with an indefinite number of sales.

id=2007-23: The planar Haj\'os calculus is the Haj\'os calculus with the restriction that all the graphs that appear in the construction (including a final graph) must be planar. We prove that the planar Haj\'os calculus is polynomially bounded iff the Haj\'os calculus is polynomially bounded.

id=2007-24: オンライン地図作成問題における目的は，探索者が未知のグラフの全ての頂点を訪問することによりグラフ構造を調査し，最後に出発点に戻ることである．ある辺の存在ならびにその長さは，探索者がその端点を訪れるまで未知である．目的達成に要した総移動距離を探索者のコストとして定める．探索対象を平面グラフとする場合，16競合のアルゴリズムが知られている．朝廣らは，探索対象をサイクルグラフとする場合において， 1.5競合のアルゴリズムを与えるとともに， $(1.25-\epsilon)$競合のアルゴリズムは存在しないことを示した（ここで$\epsilon$は任意の正定数である）．本稿では，サイクルグラフに対する最適なオンラインアルゴリズムを与える．すなわち，$\frac{1+\sqrt{3}}{2}(\simeq 1.366)$競合のアルゴリズムを与えるとともに， $(\frac{1+\sqrt{3}}{2}-\epsilon)$競合のアルゴリズムは存在しないことを証明する（上記と同様，$\epsilon$は任意の正定数である）．

id=2007-25: In the stable roommates problem, we are given 2N men and each person’s preference list. We are asked to find a stable matching, namely, a set of N pairs satisfying the stability condition. This problem is known to be solved in polynomial time; more precisely, there is a polynomial-time algorithm to find a stable matching for a given instance, or to report that a given instance has no stable matching. In this paper, we extend this problem into three-dimension, i.e., a matching is defined to be a set of triples, and show that this problem is NP-complete.

id=2007-26: The stable marriage problem is a classical matching problem introduced by Gale and Shapley. It is known that for any instance, there exists a solution, and there is a polynomial time algorithm to find one. However, the matching obtained by this algorithm is man-optimal, that is, the matching is preferable for men but unpreferable for women, (or, if we exchange the role of men and women, the resulting matching is woman-optimal). The sex-equal stable marriage problem, posed by Gusfield and Irving, asks to find a stable matching ``fair'' for both genders, namely it asks to find a stable matching with the property that the sum of the men's score is as close as possible to that of the women's. This problem is known to be strongly NP-hard. In this paper, we give a polynomial time algorithm for finding {\em a near optimal} solution in the sex-equal stable marriage problem. Furthermore, we consider the problem of optimizing additional criterion: among stable matchings that are near optimal in terms of the sex-equality, find a minimum egalitarian stable matching. We show that this problem is NP-hard, and give a polynomial time algorithm whose approximation ratio is less than two.

id=2007-27: The stable marriage problem has recently been studied in its general setting, where both ties and incomplete lists are allowed. It is NP-hard to find a stable matching of maximum size, while any stable matching is a maximal matching and thus trivially we can obtain a 2-approximation algorithm. In this paper, we give the first nontrivial result for approximation of factor less than two. Our algorithm achieves an approximation ratio of $2/(1+L^{-2})$ for instances in which only men have ties of length at most $L$. When both men and women are allowed to have ties, but the lengths are limited to two, then we show a ratio of $13/7$. We also improve the lower bound on the approximation ratio to $21/19$.

id=2007-34: Harary's generalized ticktacktoe, a kind of achievement games, have been investigated in many literatures. All animals (polyominos) except for "Snaky" have been decided whether they are winners orlosers, i.e., Snaky is a unique unsolved animal. Moreover the handicap number, which is the minimum number of stones preset by the first player before starting the play for winning the game, of the Snaky have been known only at most two. That the handicap number of an animal is zero means it is a winner. In this paper we show a winning strategy of Snaky with one handicap. From this result we can see that the handicap number of Snaky is zero or one.

id=2007-35: It has been a long-standing open problem to determine the exact randomized competitiveness of the 2-server problem, that is, the minimum competitiveness of any randomized online algorithm for the 2-server problem. For deterministic algorithms the best competitive ratio that can be obtained is 2 and no randomized algorithm is known that improves this ratio for general spaces. For the line, Bartal et al. give a $\frac{155}{78}$ competitive algorithm, but their algorithm is specific to the geometry of the line. We consider here the 2-server problem over Cross Polytope Spaces $M_{2, 4}$. We obtain an algorithm with competitive ratio of $\frac{19}{12}$, and show that this ratio is best possible. This algorithm gives the second non-trivial example of metric spaces with better than 2 competitive ratio. The algorithm uses a design technique called the knowledge state technique - a method not specific to $M_{2, 4}$.

id=2007-36: We study a variant of online scheduling problems, the online realtime scheduling. It can be defined on a complete graph, where each node represents a communication agent, and a communication between two agents can be considered as an edge. An input is a sequence of communication jobs, each of which requires two specified agents to communicate during specified time period. Each agent can participate in at most one communication job. The task of an online algorithm is to schedule jobs so that the sum of the profits of completed communication jobs is maximized. In this paper, we improve the competitive ratio of the General Shelf based Max Matching ($GSMM$) algorithm from $6 + 4 \sqrt{2} (\approx 11.66)$ to $2 \sqrt{6} + 6 (\approx 10.90)$. We also prove that this ratio is optimal for $GSMM$. In addition, we study the case where each job has no slack time, namely, it must be either started immediately or rejected at its release time, and show the competitive ratio of $GSMM$ is $2 \sqrt{6} + 5 (\approx 9.90)$.

id=2007-37: 安定ルームメイト問題は，希望リストに基づいて「安定性」を満たすように， $2N$人の人間を$N$組のペアに分割する問題である．安定ルームメイト問題は解を持たない場合もあるが，解を持つか否かを判定し，持つ場合には解を見つける多項式時間アルゴリズムが知られている．本研究ではこの問題を拡張し， $3N$人の人間を$N$組のトリプルに分割する問題を提案する．そして，この問題において解の存在を判定する問題がNP完全であることを示す．

id=2007-40: We propose an algorithm using a spectral method, and analyze its average-case performance for MAX2SAT in the planted solution model. In [SAT06], they proposed a distribution G_{n,p,r} for MAX2SAT in the planted solution model, as well as a message-passing algorithm. They showed that it solves, whp, MAX2SAT on G_{n,p,r} for rather dense formulas, i.e., the expected number of clauses is Omega(n^{1.5}\sqrt{log n}). In this paper, we propose an algorithm using a spectral method and a variant of message-passing algorithms, and show that it solves, whp, MAX2SAT on G_{n,p,r} for sparser formulas, i.e., the expected number of clauses is Omega(n log n).

id=2007-44: Given a graph $G=(V,E)$, we say that a vertex subset $S\subseteq V$ covers a vertex $v\in V$ if the edge-connectivity between $S$ and $v$ is at least a given integer $k$, and also say that $S$ covers an edge $vw\in E$ if $v$ and $w$ are covered. We propose the multi-commodity source location problem, which is such that given a vertex- and edge-weighted graph $G$, $r$ players each select $p$ vertices, and obtain a profit that is the total weight of covered vertices and edges. However, vertices selected by one player cannot be selected by the other players. The goal is to maximize the total profits of all players. We show that the \emph{price of greed}, which indicates the ratio of the total profit of cooperating players to that of selfish players, is tightly bounded by $\min\{ r,p\}$. Also when $k=2$, we obtain tight bounds for vertex-unweighted trees.

id=2007-45: オンライン実時間スケジューリング問題とは完全グラフ上で定義される問題で、入力として一連のジョブ集合が与えられる。各ジョブに対し、各ジョブが到着する時刻、到着する辺、各ジョブの締切時刻、長さがそれぞれ定められている。アルゴリズムは各ジョブが到着する時刻から締切時刻の間に各ジョブを連続して処理することで、各ジョブの長さを価値として得ることができる。各節点は同時に 2つ以上のジョブを処理することはできない。また、オンライン実時間スケジューリング問題においてアルゴリズムは到着時刻前に各ジョブの存在を知ることはできない。当該問題に対して知られていた最も良い競合比の上限はGSMMアルゴリズムの約11.66であったが、我々はGSMMアルゴリズムのより詳細な解析を行い、競合比の上限が約10.90であることを示した。また、この値がGSMMアルゴリズムの厳密な競合比であることを示した。

岩間研究室 発表論文

2007年度

[ 論文誌 ]

[ 国際会議 ]

[ 国内発表 ]

[ 解説 ]

Abstract

岩間研究室発表論文