宮崎 修一

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.

In this paper, we study two variants of the online metric matching problem. The first problem is the online metric matching problem where all the servers are placed at one of two positions in the metric space. We show that a simple greedy algorithm achieves the competitive ratio of 3 and give a matching lower bound. The second problem is the online facility assignment problem on a line, where servers have capacities, servers and requests are placed on 1-dimensional line, and the distances between any two consecutive servers are the same. We show lower bounds 1+6(&amp gt 3.44948 ), 4+733(&amp gt 4.18133 ) and 133(&amp gt 4.33333 ) on the competitive ratio when the numbers of servers are 3, 4 and 5, respectively.

In IWOCA 2019, Ruangwises and Itoh introduced stable noncrossing matchings, where participants of each side are aligned on each of two parallel lines, and no two matching edges are allowed to cross each other. They defined two stability notions, strongly stable noncrossing matching (SSNM) and weakly stable noncrossing matching (WSNM), depending on the strength of blocking pairs. They proved that a WSNM always exists and presented an O(n2)-time algorithm to find one for an instance with n men and n women. They also posed open questions of the complexities of determining existence of an SSNM and finding a largest WSNM. In this paper, we show that both problems are solvable in polynomial time. Our algorithms are applicable to extensions where preference lists may include ties, except for one case which we show to be NP-complete.

In this paper, we consider the online buffer management problem, which formulates the problem of managing network switches supporting Quality of Service guarantee. We improve competitive ratios of the 2-value multi-queue switch model, where the value of a packet is restricted to 1 or alpha(>= 1). We use a similar approach as Azar and Richter (STOC 2003 and Algorithmica 43(1-2), 2005) did for the multi-value multi-queue switch model. Namely, we show that the competitive ratio of "the relaxed model" of the 2-value multi-queue switch model is at most x = min{c + 2-c/alpha(2-c)+(c-1), c alpha}, if the competitive ratio of an online algorithm for the unit-value multi-queue switch model is at most c. Azar and Richter's technique implies that if the competitive ratio of the 2-value single-queue switch model is x', then the competitive ratio of the 2-value multi-queue switch model is at most xx'. We obtain several results using known c and x'. (C) 2017 Elsevier B.V. All rights reserved.

We consider a variant of the online buffer management problem in network switches, called the k-frame throughput maximization problem (k-FTM). This problem models the situation where a large frame is fragmented into k packets and transmitted through the Internet, and the receiver can reconstruct the frame only if he/she accepts all the k packets. Kesselman et al. introduced this problem and showed that its competitive ratio is unbounded even when k= 2. They also introduced an "order-respecting" variant of k-FTM, called k-OFTM, where inputs are restricted in some natural way. They proposed an online algorithm and showed that its competitive ratio is at most 2kB/left perpendicular B/k right perpendicular + k for any B >= k, where B is the size of the buffer. They also gave a lower bound of B/left perpendicular 2B/k right perpendicular for deterministic online algorithms when 2B >= k and k is a power of 2. In this paper, we improve upper and lower bounds on the competitive ratio of k-OFTM. Our main result is to improve an upper bound of 0 (k(2)) by Kesselman et al. to 5B+left perpendicular B/k right perpendicular-4/left perpendicular B/2k right perpendicular = 0 (k) for B >= 2k. Note that this upper bound is tight up to a multiplicative constant factor since the lower bound given by Kesselman et al. is Omega(k). We also give two lower bounds. First we give a lower bound of 2B/left perpendicular B/(k-1) right perpendicular +1 on the competitive ratio of deterministic online algorithms for any k >= 2 and any B >= k-1, which improves the previous lower bound of B/left perpendicular 2B/k right perpendicularby a factor of almost four. Next, we present the first nontrivial lower bound on the competitive ratio of randomized algorithms. Specifically, we give a lower bound of k-1 against an oblivious adversary for any k >= 3 and any B. Since a deterministic algorithm, as mentioned above, achieves an upper bound of about 10k, this indicates that randomization does not help too much. (C) 2016 Elsevier B.V. All rights reserved.

The stable marriage problem (SMP) can be seen as a typical game, where each player wants to obtain the best possible partner by manipulating his/her preference list. Thus the set Q of preference lists submitted to the matching agency may differ from P, the set of true preference lists. In this paper, we study the stability of the stated lists in Q. If Q is not Nash equilibrium, i.e., if a player can obtain a strictly better partner (with respect to the preference order in P) by only changing his/her list, then in the view of standard game theory, Q is vulnerable. In the case of SMP, however, we need to consider another factor, namely that all valid matchings should not include any "blocking pairs" with respect to P. Thus, if the above manipulation of a player introduces blocking pairs, it would prevent this manipulation. Consequently, we say Q is totally stable if either Q is a Nash equilibrium or if any attempt at manipulation by a single player causes blocking pairs with respect to P. We study the complexity of testing the total stability of a stated strategy. It is known that this question is answered in polynomial time if the instance (P, Q) always satisfies P = Q. We extend this polynomially solvable class to the general one, where P and Q may be arbitrarily different.

The Hospitals/Residents problem is a many-to-one extension of the stable marriage problem. In an instance, each hospital specifies a quota, i.e., an upper bound on the number of positions it provides. 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 in which each hospital specifies not only an upper bound but also a lower bound on its number of positions. In this setting, there can be instances that admit no stable matching, but the problem of asking if there is a stable matching is solvable in polynomial time. In case there is no stable matching, we consider the problem of finding a matching that is "as stable as possible", namely, a matching with a minimum number of blocking pairs. We show that this problem is hard to approximate within the ratio of for any positive constant where and are the sets of hospitals and residents, respectively. We then tackle this hardness from two different angles. First, we give an exponential-time exact algorithm whose running time is , where is the number of blocking pairs in an optimal solution. Second, we consider another measure for optimization criteria, i.e., the number of residents who are involved in blocking pairs. We show that this problem is still NP-hard but has a polynomial-time -approximation algorithm.

The Hospitals/Residents problem is a many-to-one generalization of the well-known Stable Marriage problem. Its instance consists of a set of residents, a set of hospitals, each resident’s preference list, each hospital’s preference list, and each hospital’s capacity (i.e., the number of available positions). It asks to find a stable matching between residents and hospitals. In this paper, we consider the problem of deciding, given residents’ preference lists and a matching, whether there are hospitals’ preference lists that make a given matching stable. We call this problem Stable Hospital’s Preference List problem (SHPL). It is easy to see that there always exists a solution if we allow arbitrary preference lists of hospitals. Considering more suitable situations, we pose a restricted version, called k-SHPL, in which there are only k kinds of preference lists of hospitals. We show that 1-SHPL is solvable in polynomial time, while k-SHPL is NP-complete for any k such that 2 ≤ k ≤ n1-e, where n is the number of residents and e is any positive constant. We also present four heuristics algorithms (first-fit algorithms) for 2-SHPL. We implement these algorithms and present a computational study using random instances.

In this paper, we study the advice complexity of the online bipartite matching problem and the online stable marriage problem. We show that for both problems, inverted right perpendicular log(2)(n!) inverted left perpendicular bits of advice are necessary and sufficient for a deterministic online algorithm to be optimal, where n denotes the number of vertices in one bipartition in the former problem, and the number of men in the latter. (C) 2014 Elsevier B.V. All rights reserved.

The problem of finding a largest stable matching where preference lists may include ties and unacceptable partners (MAX SMTI) is known to be NP-hard. It cannot be approximated within 33/29 (> 1.1379) unless P=NP, and the current best approximation algorithm achieves the ratio of 1.5. MAX SMTI remains NP-hard even when preference lists of one side do not contain ties, and it cannot be approximated within 21/19 (> 1.1052) unless P=NP. However, even under this restriction, the best known approximation ratio is still 1.5. In this paper, we improve it to 25/17 (< 1.4706).

In the stable marriage problem, any instance admits the so-called man-optimal stable matching, in which every man is assigned the best possible partner. However, there are instances for which all men receive low-ranked partners even in the man-optimal stable matching. In this paper we consider the problem of improving the man-optimal stable matching by changing only one man's preference list. We show that the optimization variant and the decision variant of this problem can be solved in time O(n3) and O(n2), respectively, where n is the number of men (women) in an input. We further extendthe problem so that we are allowed to change k men's preference lists. We show that the problem is W[1]-hard with respect to the parameter k and give O(n2k+1)-time and O(nk+1)-time exact algorithms for the optimization and decision variants, respectively. Finally, we show that the problems become easy when k = n we give O(n2.5 log n)-time and O(n2)-time algorithms for theoptimization and decision variants, respectively. © 2013 by the authors licensee MDPI, Basel, Switzerland.

Manlove and OMalley (2008) [8] proposed the Student-Project Allocation problem with Preferences over Projects (SPA-P). They proved that the problem of finding a maximum stable matching in SPA-P is APX-hard and gave a polynomial-time 2-approximation algorithm. In this paper, we give an improved upper bound of 1.5 and a lower bound of 21/19 (&gt 1.1052). © 2012 Elsevier B.V. All rights reserved.

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.

In the graph exploration problem, a searcher explores the whole set of nodes of an unknown graph. We assume that all the unknown graphs are undirected and connected. The searcher is not aware of the existence of ail 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 a tour as short as possible. One of the simplest strategies is the nearest neighbor algorithm (NN). which always chooses the unvisited node nearest to the searcher's current position. The weighted NN (WNN) is an extension of NN, which chooses the next node to visit by using the weighted distance. It is known that WNN with weight 3 is 16-competitive for planar graphs. In this paper we prove that NN achieves the competitive ratio of 1.5 for cycles. In addition, we show that the analysis for the competitive ratio of NN is tight by providing an instance for which the bound of 1.5 is attained, and NN is the best for cycles among WNN with all possible weights. Furthermore, we prove that no online algorithm to explore cycles is better than 1.25-competitive. (C) 2009 Elsevier B.V. All rights reserved.

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-ε for an arbitrary constant ε &gt 0. © 2009 by the authors.

The purpose of the online graph exploration problem is to visit all the nodes of a given graph and come back to the starting node with the minimum total traverse cost. However, unlike the classical Traveling Salesperson Problem, information of the graph is given online. When an online algorithm (called a searcher) visits a node v, then it learns information on nodes and edges adjacent to v. The searcher must decide which node to visit next depending on partial and incomplete information of the graph that it has gained in its searching process. The goodness of the algorithm is evaluated by the competitive analysis. If input graphs to be explored are restricted to trees, the depth-first search always returns an optimal tour. However, if graphs have cycles, the problem is non-trivial. In this paper we consider two simple cases. First, we treat the problem on simple cycles. Recently, Asahiro et al. proved that there is a 1.5-competitive online algorithm, while no online algorithm can be (1.25 - epsilon)-competitive for any positive constant epsilon. In this paper, we give an optimal online algorithm for this problem: namely, we give a 1+root 3/2 (approximate to 1.366)-competitive algorithm, and prove that there is no (1+root 3/2 - epsilon)-competitive algorithm for any positive constant epsilon. Furthermore, we consider the problem on unweighted graphs. We also give an optimal result; namely we give a 2-competitive algorithm and prove that there is no (2 - epsilon)-competitive online algorithm for any positive constant epsilon.

In the stable marriage problem that allows incomplete preference lists, all stable matchings for a given instance have the same size. However, if we ignore the stability, there can be larger matchings. Biro et al. defined the problem of finding a maximum cardinality matching that-contains minimum number of blocking pairs. They proved that this problem is not approximable within some constant delta > 1 unless P = NP, even when all preference lists are of length at most 3. In this paper, we improve this constant delta to n(1-epsilon) for any epsilon > 0, where n is the number of men in an input. (C) 2009 Elsevier B.V. All rights reserved.

This paper introduces a new timetabling problem on universities, called interview timetabling. In this problem, some constant number, say three, of referees are assigned to each of 2n graduate students. Our task is to construct a presentation timetable of these 2n students using n timeslots and two rooms, so that two students evaluated by the same referee must be assigned to different timeslots. The optimization goal is to minimize the total number of movements of all referees between two rooms. This problem comes from the real world in the interview timetabling in Kyoto University. We propose two restricted models of this problem, and investigate their time complexities.

The online buffer management problem formulates the problem of queuing policies of network switches supporting QOS (Quality of Service) guarantee. In this paper. we consider one of the most standard models, called multi-queue switches model. In this model. Albers et al. gave a lower bound e/e-1, and Azar et al. gave an upper bound e/e-1 on the competitive ratio when in. the number of input ports, is, large, The), are tight. but there still remains it gap for small in. In this paper, we consider the case where m = 2. namely. a switch is equipped with two ports. which is called a bicordal buffer model. We propose an online algorithm called Segmental Greedy Algorithm (SG) and show that its competitive ratio is at most 16/13(similar or equal to 1.231), improving the previous upper bound by 9/7(similar or equal to 1.286). This matches the lower bound given by Schmidt.

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 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 - 1/M min(K=1,2,...,N){[M/K] + K - 1}.

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 article, 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(&lt 1.858). We also improve the lower bound on the approximation ratio to 21/19(&gt 1.1052). © 2007 ACM.

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 log N/N for an arbitrarily positive constant. c, where N denotes the number of men in an input.

While the original stable marriage problem requires all participants to rank all members of the opposite sex in a strict order, two natural variations are to allow for incomplete preference lists and ties in the preferences. Either variation is polynomially solvable, but it has recently been shown to be NP-hard to find a maximum cardinality stable matching when both of the 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. In this paper, we give a randomized approximation algorithm RANDBRK and show that its expected approximation ratio is at most 10/7(< 1.4286) for a restricted but still NP-hard case, where ties occur in only men's lists, each man writes at most one tie, and the length of ties is two. We also show that our analysis is nearly tight by giving a lower bound 32/23(> 1.3913) for RANDBRK. Furthermore, we show that these restrictions except for the last one can be removed without increasing the approximation ratio too much. (C) 2004 Elsevier B.V. All rights reserved.

We consider instances of the classical stable marriage problem in which persons may include ties in their preference lists. We show that, in such a setting, strong lower bounds bold for the approximability of each of the problems of finding an egalitarian, minimum regret and sex-equal stable matching. We also consider stable marriage instances in which persons may express unacceptable partners in addition to ties. In this setting, we prove that there are constants delta,delta' such that each of the problems of approximating a maximum and minimum cardinality stable matching within factors of delta,delta' (respectively) is NP-hard, under strong restrictions. We also give an approximation algorithm for both problems that has a performance guarantee expressible in terms of the number of lists with ties. This significantly improves on the best-known previous performance guarantee, for the case that the ties are sparse. Our results have applications to large-scale centralized matching schemes. (C) 2003 Elsevier B.V. All rights reserved.

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

We study the online version of the independent set problem in graphs. The vertices of an input graph are given one by one along with their edges to previous vertices, and the task is to decide whether to add each given vertex to an independent set solution. The goal is to maximize the size of the independent set, relative to the size of the optimal independent set. Since it is known that no online algorithm can attain competitive ratio better than n - 1, where n denotes the number of vertices, we study here relaxations where the algorithm can hedge its bets by maintaining multiple alternative solutions. We introduce two models. In the first model, the algorithm can maintain a multiple number (r(n)) of solutions (independent sets) and choose the largest one as the final solution. We show that the best competitive ratio for this model is theta(n/log n) when r(n) is a polynomial and theta(n) when r(n) is a constant. In the second more powerful model, the algorithm can copy intermediate solutions and extend the copied solutions in different ways. We obtain an upper bound O(n/log n) and a lower bound Omega(n/log(3)n) for the best possible competitive ratio when r(n) is a polynomial. Furthermore, we show a tight theta(n) bound when r(n) is a constant. Lower bound results of this paper hold also for randomized online algorithms against an oblivious adversary. (C) 2002 Elsevier Science B.V. All rights reserved.

The Stable Marriage Problem and its many variants have been widely studied in the literature (Gusfield and Irving, The Stable Marriage Problem: Structure and Algorithms, MIT Press, Cambridge, MA, 1989; Roth and Sotomayor, Two-sided matching: a study in game-theoretic modeling and analysis, Econometric Society Monographs, vol. 18, Cambridge University Press, Cambridge, 1990; Knuth, Stable Marriage and its Relation to Other Combinatorial Problems, CRM Proceedings and Lecture Notes, vol. 10, American Mathematical Society, Providence, RI, 1997), partly because of the inherent appeal of the problem, partly because of the elegance of the associated structures and algorithms, and partly because of important practical applications, such as the National Resident Matching Program (Roth, J. Political Economy 92(6) (1984) 991) and similar large-scale matching schemes. Here, we present the first comprehensive study of variants of the problem in which the preference lists of the participants are not necessarily complete and not necessarily totally ordered. We show that, under surprisingly restrictive assumptions, a number of these variants are hard, and hard to approximate. The key observation is that, in contrast to the case where preference lists are complete or strictly ordered (or both), a given problem instance may admit stable matchings of different sizes. In this setting, examples of problems that are hard are: finding a stable matching of maximum or minimum size, determining whether a given pair is stable-even if the indifference takes the form of ties on one side only, the ties are at the tails of lists, there is at most one tie per list, and each tie is of length 2; and finding, or approximating, both an 'egalitarian' and a 'minimum regret' stable matching. However, we give a 2-approximation algorithm for the problems of finding a stable matching of maximum or minimum size. We also discuss the significant implications of our results for practical matching schemes. (C) 2002 Elsevier Science B.V. All rights reserved.

本研究の目的は，和積形論理式の充足可能性問題（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完全集合による近似は, 組合せアルゴリズムを実験的に評価する際の例題生成の効率に深いかかわりをもっている.