宮崎 修一

In the online facility assignment problem [Formula: see text], there exist [Formula: see text] servers [Formula: see text] on a metric space where each [Formula: see text] has an integer capacity [Formula: see text] and a request arrives one-by-one. The task of an online algorithm is to irrevocably match a current request with one of the servers with vacancies before the next request arrives. As special cases for [Formula: see text], we consider [Formula: see text] on a line , which is denoted by [Formula: see text] and [Formula: see text], where the latter is the case of [Formula: see text] with equidistant servers. In this paper, we perform the competitive analysis for the above problems. As a natural generalization of the greedy algorithm grdy, we introduce a class of algorithms called MPFS (Most Preferred Free Servers) and show that any MPFS algorithm has the capacity-insensitive property, i.e., for any MPFS algorithm alg for [Formula: see text], if alg is [Formula: see text]-competitive when [Formula: see text], then alg is [Formula: see text]-competitive for general [Formula: see text]. By applying the capacity-insensitive property of the greedy algorithm grdy, we derive the matching upper and lower bounds [Formula: see text] on the competitive ratio of grdy for [Formula: see text]. To investigate the capability of MPFS algorithms, we show that the competitive ratio of any MPFS algorithm alg for [Formula: see text] is at least [Formula: see text]. Then, we propose a new MPFS algorithm idas (Interior Division for Adjacent Servers) for [Formula: see text] and show that the competitive ratio of idas for [Formula: see text] is at most [Formula: see text], i.e., idas for [Formula: see text] is best possible in all the MPFS algorithms. We also give numerical experiments to investigate the performance of idas and grdy and show that idas performs better than grdy for distribution of request sequences with locality.

This paper has two objectives. One is to give a linear time algorithm that solves the stable roommates problem (i.e., obtains one stable matching) using the stable marriage problem. The idea is that a stable matching of a roommate instance [Formula: see text] is a stable matching (that however must satisfy a certain condition) of some marriage instance [Formula: see text]. [Formula: see text] is obtained just by making two copies of [Formula: see text], one for the men’s table and the other for the women’s table. The second objective is to investigate the possibility of reducing the roommate problem to the marriage problem (with one-to-one correspondence between their stable matchings) in polynomial time. For a given [Formula: see text], we construct the rotation POSET [Formula: see text] of [Formula: see text] and then we “halve” it to obtain [Formula: see text], by which we can forget the above condition and can use all the closed subsets of [Formula: see text] for all the stable matchings of [Formula: see text]. Unfortunately this approach works (runs in polynomial time) only for restricted instances.

In the online metric matching problem, there are servers on a given metric space and requests are given one-by-one. The task of an online algorithm is to match each request immediately and irrevocably with one of the unused servers. In this paper, we pursue competitive analysis for two variants of the online metric matching problem. The first variant is a restriction where each server is placed at one of two positions, which is denoted by OMM([Formula: see text]). We show that a simple greedy algorithm achieves the competitive ratio of 3 for OMM([Formula: see text]). We also show that this greedy algorithm is optimal by showing that the competitive ratio of any deterministic online algorithm for OMM([Formula: see text]) is at least 3. The second variant is the online facility assignment problem on a line. In this problem, the metric space is a line, the servers have capacities, and the distances between any two consecutive servers are the same. We denote this problem by OFAL([Formula: see text]), where [Formula: see text] is the number of servers. We first observe that the upper and lower bounds for OMM([Formula: see text]) also hold for OFAL([Formula: see text]), so the competitive ratio for OFAL([Formula: see text]) is exactly 3. We then show lower bounds on the competitive ratio [Formula: see text] [Formula: see text], [Formula: see text] [Formula: see text] and [Formula: see text] [Formula: see text] for OFAL([Formula: see text]), OFAL([Formula: see text]) and OFAL([Formula: see text]), respectively.

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 favorable for men but unfavorable for women, (or, if we exchange the roles of men and women, the resulting matching is woman-optimal). The sex-equal stable marriage problem, posed by Gusfield and Irving, seeks a stable matching “fair” for both genders. Specifically it seeks a stable matching with the property that the sum of the men's scores 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 a near optimal solution for the sex-equal stable marriage problem. Furthermore, we consider the problem of optimizing an 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 strongly NP-hard, and give a polynomial time algorithm whose approximation ratio is less than two.

急増する不正アクセスに対応しつつ,かつ,教育研究機関としての柔軟な研究環境を維持するため,京都大学では従来の自由度は高い不正アクセスにさらされるネットワークKUINS-IIと並行に,学外と直接の通信はできないなど制約はあるが安全性の高いネットワークKUINS-IIIを新たに構築した.本論文では,KUINS-IIIの設計概念,その構成・運用について述べる.また,KUINS-IIIのセキュリティ対策の一例として,利用者が学外との通信のためKUINS-IIIのVLANにNAT装置を設置した場合でも,Policy RoutingによりNAT装置の内側の通信をKUINS-IIIのIDSで検査した後にNAT装置を通過させる手法,更に,最近のDDoS攻撃などに対し,幹線ネットワークの高帯域化だけでなく,意図的にボトルネックとなる装置を設置し,当該装置での通信断によりDDoSの影響がキャンパスLAN全体に波及しないネットワーク構成について述べる.

本研究の目的は，和積形論理式の充足可能性問題（SAT）の解法アルゴリズムである局所探索法の高速化である．局所探索法のアルゴリズムGSATに対し，実働化時の工夫と並列化によって高速化を試みる．SelmanとKautzのGSATを元に，(i)~データ構造の改良，(ii)~ベクトル並列計算機上でのベクトル化，(iii)~PVMを使った40? CPUによる並列化，を行った．これにより，合計600倍の高速化を達成した．2nd DIMACS Implementation Challenge Satisfiabilityのベンチマーク例題に対して我々のGSATを実行させたところ，既存のプログラムで解けている例題では実行時間がかなり短縮された．また，GSATを改良した局所探索法に本論文の手法を適用させることにより，既存のプログラムでは解けなかった例題を解くまでに至った．The purpose of this paper is to speed up the local search algorithmfor CNF Satisfiability problem by implementation techniques andparallelization. We selected GSAT by Selman and Kautz and attemptedspeedup by the following techniques: (i)~An improvement of the datastructure of Selman and Kautz's implementation. (ii)~Vectorization ona parallel vector supercomputer. (iii)~Parallelization using ParallelVirtual Machine (PVM). By these attempts, we achieved 600-timesspeedup in total. We executed our GSAT for benchmark instances of the2nd DIMACS Implementation Challenge, Satisfiability. Our programperformed much better than existing programs on most instances.Moreover, we were able to solve some instances that existing programscould not have solved.

クラスC_1に属する集合L_1が, クラスC_>2に属する集合L_2の部分集合であるとき, L_1はL_2の近似であると言う.L_1⊂L'_1であり, L'_1-L_>1が無限集合となるような近似L'_1が存在しないとき, L_1は最適近似であると言う.C_1がクラスP, C_2がクラスNPである場合には, P≠NPならば弱い条件のもとで最適な近似が存在しないことが示されている.本論文では, C_1がNP完全集合のクラスで, C_2がcoNPである場合に対し, 同様の結果を示す./coNP集合のNP完全集合による近似は, 組合せアルゴリズムを実験的に評価する際の例題生成の効率に深いかかわりをもっている.