The Experts below are selected from a list of 7623 Experts worldwide ranked by ideXlab platform
Kazuo Iwama - One of the best experts on this subject based on the ideXlab platform.
-
a 25 17 approximation algorithm for the Stable Marriage problem with one sided ties
European Symposium on Algorithms, 2010Co-Authors: Kazuo Iwama, Shuichi Miyazaki, Hiroki YanagisawaAbstract: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).
-
improved approximation results for the Stable Marriage problem
ACM Transactions on Algorithms, 2007Co-Authors: Magnus M Halldorsson, Kazuo Iwama, Shuichi Miyazaki, Hiroki YanagisawaAbstract: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 p 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(1.1052).
-
a 1 875 approximation algorithm for the Stable Marriage problem
Symposium on Discrete Algorithms, 2007Co-Authors: Kazuo Iwama, Shuichi Miyazaki, Naoya YamauchiAbstract: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 known to be APX-hard, and the current best known approximation algorithm achieves the approximation ratio 2-c 1/√N, where c is some positive constant. In this paper, we give a 1.875-approximation algorithm, which is the first result on the approximation ratio better than two.
-
Hard variants of Stable Marriage
2002Co-Authors: David F. Manlove, Robert W Irving, Kazuo Iwama, Shuichi Miyazaki, Yasufumi MoritaAbstract:The Stable Marriage Problem and its many variants have been widely studied in the literature [6, 22, 15], 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 [20] 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
Katarzyna Paluch - One of the best experts on this subject based on the ideXlab platform.
-
strongly Stable matchings in time o nm and extension to the hospitals residents problem
ACM Transactions on Algorithms, 2007Co-Authors: Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, Katarzyna PaluchAbstract:An instance of the Stable Marriage problem is an undirected bipartite graph G e (X ∪ W, E) with linearly ordered adjacency lists with ties allowed in the ordering. A matching M is a set of edges, no two of which share an endpoint. An edge e e (a, b) ∈ Es M is a blocking edge for M if a is either unmatched or strictly prefers b to its partner in M, and b is unmatched, strictly prefers a to its partner in M, or is indifferent between them. A matching is strongly Stable if there is no blocking edge with respect to it. We give an O(nm) algorithm for computing strongly Stable matchings, where n is the number of vertices and m the number of edges. The previous best algorithm had running time O(m2). We also study this problem in the hospitals-residents setting, which is a many-to-one extension of the aforementioned problem. We give an O(m ∑h∈Hph) algorithm for computing a strongly Stable matching in the hospitals-residents problem, where ph is the quota of a hospital h. The previous best algorithm had running time O(m2).
-
strongly Stable matchings in time o nm and extension to the hospitals residents problem
Symposium on Theoretical Aspects of Computer Science, 2004Co-Authors: Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, Katarzyna PaluchAbstract:An instance of the Stable Marriage problem is an undirected bipartite graph G = (X ∪ W, E) with linearly ordered adjacency lists; ties are allowed. A matching M is a set of edges no two of which share an endpoint. An edge \(e = (a,b) \in E \ M\) is a blocking edge for M if a is either unmatched or strictly prefers b to its partner in M, and b is either unmatched or strictly prefers a to its partner in M or is indifferent between them. A matching is strongly Stable if there is no blocking edge with respect to it. We give an O(nm) algorithm for computing strongly Stable matchings, where n is the number of vertices and m is the number of edges. The previous best algorithm had running time O(m 2).
-
strongly Stable matchings in time o nm and extension to the hospitals residents problem
Lecture Notes in Computer Science, 2004Co-Authors: Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, Katarzyna PaluchAbstract:An instance of the Stable Marriage problem is an undirected bipartite graph G = (X ? W, E) with linearly ordered adjacency lists; ties are allowed. A matching M is a set of edges no two of which share an endpoint. An edge e = (a,b) ∈ E \ M is a blocking edge for M if a is either unmatched or strictly prefers b to its partner in M, and b is either unmatched or strictly prefers a to its partner in M or is indifferent between them. A matching is strongly Stable if there is no blocking edge with respect to it. We give an O(nm) algorithm for computing strongly Stable matchings, where n is the number of vertices and m is the number of edges. The previous best algorithm had running time O(m 2 ). We also study this problem in the hospitals-residents setting, which is a many-to-one extension of the above problem. We give an O(m(|R| + Σ h ∈ H p h )) algorithm for computing a strongly Stable matching in the hospitals-residents problem, where |R| is the number of residents and p h is the quota of a hospital h. The previous best algorithm had running time O(m 2 ).
Yuval Filmus - One of the best experts on this subject based on the ideXlab platform.
-
the complexity of the comparator circuit value problem
ACM Transactions on Computation Theory, 2014Co-Authors: Stephen A Cook, Yuval FilmusAbstract:In 1990, Subramanian [1990] defined the complexity class CC as the set of problems log-space reducible to the comparator circuit value problem (CCV). He and Mayr showed that NL ⊆ CC ⊆ P, and proved that in addition to CCV several other problems are complete for CC, including the Stable Marriage problem, and finding the lexicographically first maximal matching in a bipartite graph. Although the class has not received much attention since then, we are interested in CC because we conjecture that it is incomparable with the parallel class NC which also satisfies NL ⊆ NC ⊆ P, and note that this conjecture implies that none of the CC-complete problems has an efficient polylog time parallel algorithm. We provide evidence for our conjecture by giving oracle settings in which relativized CC and relativized NC are incomparable.We give several alternative definitions of CC, including (among others) the class of problems computed by uniform polynomial-size families of comparator circuits supplied with copies of the input and its negation, the class of problems AC0-reducible to Ccv, and the class of problems computed by uniform AC0 circuits with AXccv gates. We also give a machine model for CC, which corresponds to its characterization as log-space uniform polynomial-size families of comparator circuits. These various characterizations show that CC is a robust class. Our techniques also show that the corresponding function class FCC is closed under composition. The main technical tool we employ is universal comparator circuits.Other results include a simpler proof of NL ⊆ CC, a more careful analysis showing the lexicographically first maximal matching problem and its variants are CC-complete under AC0 many-one reductions, and an explanation of the relation between the Gale--Shapley algorithm and Subramanian’s algorithm for Stable Marriage.This article continues the previous work of Cook et al. [2011], which focused on Cook-Nguyen style uniform proof complexity, answering several open questions raised in that article.
-
the complexity of the comparator circuit value problem
arXiv: Computational Complexity, 2012Co-Authors: Stephen A Cook, Yuval FilmusAbstract:In 1990 Subramanian defined the complexity class CC as the set of problems log-space reducible to the comparator circuit value problem (CCV). He and Mayr showed that NL \subseteq CC \subseteq P, and proved that in addition to CCV several other problems are complete for CC, including the Stable Marriage problem, and finding the lexicographically first maximal matching in a bipartite graph. We are interested in CC because we conjecture that it is incomparable with the parallel class NC which also satisfies NL \subseteq NC \subseteq P, and note that this conjecture implies that none of the CC-complete problems has an efficient polylog time parallel algorithm. We provide evidence for our conjecture by giving oracle settings in which relativized CC and relativized NC are incomparable. We give several alternative definitions of CC, including (among others) the class of problems computed by uniform polynomial-size families of comparator circuits supplied with copies of the input and its negation, the class of problems AC^0-reducible to CCV, and the class of problems computed by uniform AC^0 circuits with CCV gates. We also give a machine model for CC, which corresponds to its characterization as log-space uniform polynomial-size families of comparator circuits. These various characterizations show that CC is a robust class. The main technical tool we employ is universal comparator circuits. Other results include a simpler proof of NL \subseteq CC, and an explanation of the relation between the Gale-Shapley algorithm and Subramanian's algorithm for Stable Marriage. This paper continues the previous work of Cook, Le and Ye which focused on Cook-Nguyen style uniform proof complexity, answering several open questions raised in that paper.
Niedermeier Rolf - One of the best experts on this subject based on the ideXlab platform.
-
Bribery and Control in Stable Marriage
2021Co-Authors: Boehmer Niclas, Bredereck Robert, Heeger Klaus, Niedermeier RolfAbstract:We initiate the study of external manipulations in Stable Marriage by considering several manipulative actions as well as several "desirable" manipulation goals. For instance, one goal is to make sure that a given pair of agents is matched in a Stable solution, and this may be achieved by the manipulative action of reordering some agents' preference lists. We present a comprehensive study of the computational complexity of all problems arising in this way. We find several polynomial-time solvable cases as well as NP-hard ones. For the NP-hard cases, focusing on the natural parameter "budget" (that is, the number of manipulative actions), we also perform a parameterized complexity analysis and encounter parameterized hardness results.Comment: Accepted to SAGT 202
-
Parameterized Complexity of Stable Roommates with Ties and Incomplete Lists Through the Lens of Graph Parameters
2021Co-Authors: Bredereck Robert, Heeger Klaus, Knop Dušan, Niedermeier RolfAbstract:We continue and extend previous work on the parameterized complexity analysis of the NP-hard Stable Roommates with Ties and Incomplete Lists problem, thereby strengthening earlier results both on the side of parameterized hardness as well as on the side of fixed-parameter tractability. Other than for its famous sister problem Stable Marriage which focuses on a bipartite scenario, Stable Roommates with Incomplete Lists allows for arbitrary acceptability graphs whose edges specify the possible matchings of each two agents (agents are represented by graph vertices). Herein, incomplete lists and ties reflect the fact that in realistic application scenarios the agents cannot bring all other agents into a linear order. Among our main contributions is to show that it is W[1]-hard to compute a maximum-cardinality Stable matching for acceptability graphs of bounded treedepth, bounded tree-cut width, and bounded disjoint paths modulator number (these are each time the respective parameters). However, if we `only' ask for perfect Stable matchings or the mere existence of a Stable matching, then we obtain fixed-parameter tractability with respect to tree-cut width but not with respect to treedepth. On the positive side, we also provide fixed-parameter tractability results for the parameter feedback edge set number.Comment: An extended abstract of this paper appears at ISAAC 201
-
Multidimensional Stable Roommates with Master List
2021Co-Authors: Bredereck Robert, Heeger Klaus, Knop Dušan, Niedermeier RolfAbstract:Since the early days of research in algorithms and complexity, the computation of Stable matchings is a core topic. While in the classic setting the goal is to match up two agents (either from different "gender" (this is Stable Marriage) or "unrestricted" (this is Stable Roommates)), Knuth [1976] triggered the study of three- or multidimensional cases. Here, we focus on the study of Multidimensional Stable Roommates, known to be NP-hard since the early 1990's. Many NP-hardness results, however, rely on very general input instances that do not occur in at least some of the specific application scenarios. With the quest for identifying islands of tractability for Multidimensional Stable Roommates, we study the case of master lists. Here, as natural in applications where agents express their preferences based on "objective" scores, one roughly speaking assumes that all agent preferences are "derived from" a central master list, implying that the individual agent preferences shall be similar. Master lists have been frequently studied in the two-dimensional (classic) Stable matching case, but seemingly almost never for the multidimensional case. This work, also relying on methods from parameterized algorithm design and complexity analysis, performs a first systematic study of Multidimensional Stable Roommates under the assumption of master lists
-
Multidimensional Stable Roommates with Master List
2020Co-Authors: Bredereck Robert, Heeger Klaus, Knop Dušan, Niedermeier RolfAbstract:Since the early days of research in algorithms and complexity, the computation of Stable matchings is a core topic. While in the classic setting the goal is to match up two agents (either from different "gender" (this is Stable Marriage) or "unrestricted" (this is Stable Roommates)), Knuth [1976] triggered the study of three- or multidimensional cases. Here, we focus on the study of Multidimensional Stable Roommates, known to be NP-hard since the early 1990's. Many NP-hardness results, however, rely on very general input instances that do not occur in at least some of the specific application scenarios. With the quest for identifying islands of tractability, we look at the case of master lists. Here, as natural in applications where agents express their preferences based on "objective" scores, one roughly speaking assumes that all agent preferences are "derived from" a central master list, implying that the individual agent preferences shall be similar. Master lists have been frequently studied in the two-dimensional (classic) Stable matching case, but seemingly almost never for the multidimensional case. This work, also relying on methods from parameterized algorithm design and complexity analysis, performs a first systematic study of Multidimensional Stable Roommates under the assumption of master lists
Shuichi Miyazaki - One of the best experts on this subject based on the ideXlab platform.
-
strategy proof approximation algorithms for the Stable Marriage problem with ties and incomplete lists
arXiv: Computer Science and Game Theory, 2019Co-Authors: Koki Hamada, Shuichi Miyazaki, Hiroki YanagisawaAbstract:In the Stable Marriage problem (SM), a mechanism that always outputs a Stable matching is called a Stable mechanism. One of the well-known Stable mechanisms is the man-oriented Gale-Shapley algorithm (MGS). MGS has a good property that it is strategy-proof to the men's side, i.e., no man can obtain a better outcome by falsifying a preference list. We call such a mechanism a man-strategy-proof mechanism. Unfortunately, MGS is not a woman-strategy-proof mechanism. Roth has shown that there is no Stable mechanism that is simultaneously man-strategy-proof and woman-strategy-proof, which is known as Roth's impossibility theorem. In this paper, we extend these results to the Stable Marriage problem with ties and incomplete lists (SMTI). Since SMTI is an extension of SM, Roth's impossibility theorem takes over to SMTI. Therefore, we focus on the one-sided-strategy-proofness. In SMTI, one instance can have Stable matchings of different sizes, and it is natural to consider the problem of finding a largest Stable matching, known as MAX SMTI. Thus we incorporate the notion of approximation ratio used in the theory of approximation algorithms. We say that a Stable-mechanism is $c$-approximate-Stable mechanism if it always returns a Stable matching of size at least $1/c$ of a largest one. We also consider a restricted variant of MAX SMTI, which we call MAX SMTI-1TM, where only men's lists can contain ties. Our results are summarized as follows: (i) MAX SMTI admits both a man-strategy-proof 2-approximate-Stable mechanism and a woman-strategy-proof 2-approximate-Stable mechanism. (ii) MAX SMTI-1TM admits a woman-strategy-proof 2-approximate-Stable mechanism. (iii) MAX SMTI-1TM admits a man-strategy-proof 1.5-approximate-Stable mechanism. All these results are tight in terms of approximation ratios. Also, all these strategy-proofness results apply for strategy-proofness against coalitions.
-
a 25 17 approximation algorithm for the Stable Marriage problem with one sided ties
European Symposium on Algorithms, 2010Co-Authors: Kazuo Iwama, Shuichi Miyazaki, Hiroki YanagisawaAbstract: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).
-
improved approximation results for the Stable Marriage problem
ACM Transactions on Algorithms, 2007Co-Authors: Magnus M Halldorsson, Kazuo Iwama, Shuichi Miyazaki, Hiroki YanagisawaAbstract: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 p 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(1.1052).
-
a 1 875 approximation algorithm for the Stable Marriage problem
Symposium on Discrete Algorithms, 2007Co-Authors: Kazuo Iwama, Shuichi Miyazaki, Naoya YamauchiAbstract: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 known to be APX-hard, and the current best known approximation algorithm achieves the approximation ratio 2-c 1/√N, where c is some positive constant. In this paper, we give a 1.875-approximation algorithm, which is the first result on the approximation ratio better than two.
-
Hard variants of Stable Marriage
2002Co-Authors: David F. Manlove, Robert W Irving, Kazuo Iwama, Shuichi Miyazaki, Yasufumi MoritaAbstract:The Stable Marriage Problem and its many variants have been widely studied in the literature [6, 22, 15], 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 [20] 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
