The Stable Roommates Problem with Choice Functions

The stable marriage theorem of Gale and Shapley states that for n men and n women there always exists a stable marriage scheme, that is, a set of marriages such that no man and woman mutually prefer one another to their partners. The stable marriage theorem was generalized in two directions: the stable roommates problem is the “one-sided” version, where any two agents on the market can form a partnership. The generalization by Kelso and Crawford is in the “two-sided” model, but on one side of the market agents have a so-called substitutable choice function, and stability is interpreted in a natural way. It turned out that even if both sides of the market have substitutable choice functions, there still exists a stable assignment. The latter version contains the “many-to-many” model where up to a personal quota, polygamy is allowed for both men and women in the two-sided market.     

A diagrammatic classification in a combinatorial problem: the case of the stable marriage problem

The stable marriage problem (SMP) is a combinatorial problem to find stable matching between n women and n men given a complete preference list of men over women and vice versa. An instance of the SMP can be expressed by a bipartite graph with multiple (weighted) edges. By rearranging the graph, we use a diagram that involves several constraints to visualize several symmetries. By the diagram, all instances of the size-three SMP (three women and three men) are classified. The classification may be supported by the fact that the same class has the same stable matching.     

Antibody-based computing: an application to the stable marriage problem

Antibodies, among other things, are important components of the immune system. This paper proposes using the specific recognition capability exhibited by antibodies for computation, in particular, for solving the stable marriage problem, which has been studied as a combinatorial computational problem. Antibody-based computation is proposed by integrating the recognition capabilities of antibodies. The computation is carried out on an array form that is suitable not only for expressing stable marriage problems, but also for further integration to antibody microarrays. This work was presented in part at the 12th International Symposium on Artificial Life and Robotics, Oita, Japan, January 25–27, 2007     

Manipulation complexity and gender neutrality in stable marriage procedures

The stable marriage problem is a well-known problem of matching men to women so that no man and woman who are not married to each other both prefer each other. Such a problem has a wide variety of practical applications, ranging from matching resident doctors, to hospitals to matching students to schools. A well-known algorithm to solve this problem is the Gale–Shapley algorithm, which runs in quadratic time in the number of men/women. It has been proven that stable marriage procedures can always be manipulated. Whilst the Gale–Shapley algorithm is computationally easy to manipulate, we prove that there exist stable marriage procedures which are NP-hard to manipulate. We also consider the relationship between voting theory and stable marriage procedures, showing that voting rules which are NP-hard to manipulate can be used to define stable marriage procedures which are themselves NP-hard to manipulate. Finally, we consider the issue that stable marriage procedures like Gale–Shapley favour one gender over the other, and we show how to use voting rules to make any stable marriage procedure gender neutral.     

A network visualization of stable matching in the stable marriage problem

The stable marriage problem (SMP) seeks matchings between n women and n men which would result in stability, and not lead to divorce or extramarital affairs. We have introduced a network consisting of nodes which represent matchings, and links between nodes which attain stability by exchanging a partner between two pairs. The network is depicted with nodes laid out to involve several coordinates which indicate either women’s satisfaction or men’s or both. With the network visualization, regularity and symmetry can be made conspicuous in specific instances of the SMP such as the Latin SMP.     

Polynomial time algorithm for an optimal stable assignment with multiple partners

This paper considers the many-to-many version of the stable marriage problem where each man and woman has a strict preference ordering on the members of the opposite sex that he or she considers acceptable. Further, each man and woman wishes to be matched to as many acceptable partners as possible, up to his or her specified quota. In this setup, a polynomial time algorithm for finding a stable matching that minimizes the sum of partner ranks across all men and women is provided. It is argued that this sum can be used as an optimality criterion for minimizing total dissatisfaction if the preferences over partner-combinations satisfy a no-complementarities condition. The results in this paper extend those already known for the one-to-one version of the problem.     

Three-Sided Stable Matchings with Cyclic Preferences

Knuth (Mariages Stables, Les Presses de L’Université de Montréal, 1976) asked whether the stable matching problem can be generalised to three dimensions, e.g., for families containing a man, a woman and a dog. Subsequently, several authors considered the three-sided stable matching problem with cyclic preferences, where men care only about women, women only about dogs, and dogs only about men. In this paper we prove that if the preference lists may be incomplete, then the problem of deciding whether a stable matching exists, given an instance of the three-sided stable matching problem with cyclic preferences, is NP-complete. Considering an alternative stability criterion, strong stability, we show that the problem is NP-complete even for complete lists. These problems can be regarded as special types of stable exchange problems, therefore these results have relevance in some real applications, such as kidney exchange programs.     

Understanding the Generalized Median Stable Matchings

Let I be a stable matching instance with N stable matchings. For each man m, order his (not necessarily distinct) N partners from his most preferred to his least preferred. Denote the ith woman in his sorted list as p _i (m). Let α _i consist of the man-woman pairs where each man m is matched to p _i (m). Teo and Sethuraman proved this surprising result: for i=1 to N, not only is α _i a matching, it is also stable. The α _i ’s are called the generalized median stable matchings of I. Determining if these stable matchings can be computed efficiently is an open problem.     

A Tight Lower Bound for Computing the Diameter of a 3D Convex Polytope

The diameter of a set P of n points in ℝ ^d is the maximum Euclidean distance between any two points in P. If P is the vertex set of a 3-dimensional convex polytope, and if the combinatorial structure of this polytope is given, we prove that, in the worst case, deciding whether the diameter of P is smaller than 1 requires Ω(nlog n) time in the algebraic computation tree model. It shows that the O(nlog n) time algorithm of Ramos for computing the diameter of a point set in ℝ³ is optimal for computing the diameter of a 3-polytope. We also give a linear time reduction from Hopcroft’s problem of finding an incidence between points and lines in ℝ² to the diameter problem for a point set in ℝ⁷.     

Selection of formal verification heuristics for parallel execution

Functional verification is “the” major design-phase bottleneck for silicon productivity. Since functional verification is an NP-complete problem, it relies on a large number of heuristics with associated parameters (engines). With the advent of parallel processing, formal verification can be optimized by selecting the best n engines to run in parallel, increasing the chance of reaching successful termination of the verification task. In this paper, we will present a methodology to build engine estimators based on structural metrics and to select n engines to run in parallel. The methodology considers both engines’ estimated performance and engines’ correlation. Results confirmed that the methodology can be a very quick selection mechanism for parallelization of engines in order to increase the chance of running the best engines to solve the problem.     

An improved approximation lower bound for finding almost stable maximum matchings

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. Biró 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 δ>1 unless P=NP, even when all preference lists are of length at most 3. In this paper, we improve this constant δ to n1−ε for any ε>0, where n is the number of men in an input.     

Solution of continuous problems of optimal covering with spheres using optimal set-partition theory

The paper considers a continuous problem of optimal c-sphere covering of a compact set from Ω from E _n with a given number of spheres of minimum radius and a problem of covering a set with the minimum number of spheres of given radius. Algorithms are proposed and substantiated to solve the problems using optimal set-partition theory and Shor’s r-algorithm. Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 98–117, May–June 2009.     

A constructive approach to constrained hexahedral mesh generation

Mitchell proved that a necessary and sufficient condition for the existence of a topological hexahedral mesh constrained to a quadrilateral mesh on the sphere is that the constraining quadrilateral mesh contains an even number of elements. Mitchell’s proof depends on Smale’s theorem on the regularity of curves on compact manifolds. Although the question of the existence of constrained hexahedral meshes has been solved, the known solution is not easily programmable; indeed, there are cases, such as Schneider’s Pyramid, that are not easily solved. Eppstein later utilized portions of Mitchell’s existence proof to demonstrate that hexahedral mesh generation has linear complexity. In this paper, we demonstrate a constructive proof to the existence theorem for the sphere, as well as assign an upper-bound to the constant of the linear term in the asymptotic complexity measure provided by Eppstein. Our construction generates 76 × n hexahedra elements within the solid where n is the number of quadrilaterals on the boundary. The construction presented is used to solve some problems posed by Schneiders and Eppstein. We will also use the results provided in this paper, in conjunction with Mitchell’s Geode-Template, to create an alternative way of creating a constrained hexahedral mesh. The construction utilizing the Geode-Template requires 130 × n hexahedra, but will have fewer topological irregularities in the final mesh.     

Minimum Weakly Fundamental Cycle Bases Are Hard To Find

In the last years, new variants of the minimum cycle basis (MCB) problem and new classes of cycle bases have been introduced, as motivated by several applications from disparate areas of scientific and technological inquiry. At present, the complexity status of the MCB problem is settled only for undirected, directed, and strictly fundamental cycle bases (SFCB’s). Weakly fundamental cycle bases (WFCB’s) form a natural superclass of SFCB’s. A cycle basis of a graph G is a WFCB iff ν=0 or there exists an edge e of G and a circuit C _i in such that is a WFCB of G∖e. WFCB’s still possess several of the nice properties offered by SFCB’s. At the same time, several classes of graphs enjoying WFCB’s of cost asymptotically inferior to the cost of the cheapest SFCB’s have been found and exhibited in the literature. Considered also the computational difficulty of finding cheap SFCB’s, these works advocated an in-depth study of WFCB’s. In this paper, we settle the complexity status of the MCB problem for WFCB’s (the MWFCB problem). The problem turns out to be -hard. However, in this paper, we also offer a simple and practical 2⌈log ₂ n⌉-approximation algorithm for the MWFCB problem. In O(n ν) time, this algorithm actually returns a WFCB whose cost is at most 2⌈log ₂ n⌉∑ _e∈E(G) w _e , thus allowing a fast 2⌈log ₂ n⌉-approximation also for the MCB problem. With this algorithm, we provide tight bounds on the cost of any MCB and MWFCB.     

A Polynomial-Time Algorithm to Find von Neumann-Morgenstern Stable Matchings in Marriage Games

This paper considers von Neumann-Morgenstern (vNM) stable sets in marriage games. Ehlers (Journal of Economic Theory 134: 537–547, 2007) showed that if a vNM stable set exists in a marriage game, the set is a maximal distributive lattice of matchings that includes all core matchings. To determine what matchings form a vNM stable set, we propose a polynomial-time algorithm that finds a man-optimal matching and a woman-optimal matching in a vNM stable set of a given marriage game. This algorithm also generates a modified preference profile such that a vNM stable set is obtained as the core of a marriage game with the modified preference profile. It is well known that cores of marriage games are nonempty. However, the nonemptiness of cores does not imply the existence of a vNM stable set. It is proved using our algorithm that there exists a unique vNM stable set for any marriage game.     

An Efficient Algorithm for Batch Stability Testing

Given a stable marriage problem instance represented by a bipartite graph having 2n vertices and m edges, we describe an algorithm that can verify the stability of k different matchings in a batch fashion in O((m+kn)log ² n) time. This affirmatively answers a longstanding open question of Gusfield and Irving as to whether stability can be verified in a batch setting (after sufficient preprocessing) in time sub-quadratic in n.     

A Formal Logic Approach to Constrained Combinatorial Testing

Combinatorial testing is as an effective testing technique to reveal failures in a given system, based on input combinations coverage and combinatorial optimization. Combinatorial testing of strength t (t ≥ 2) requires that each t-wise tuple of values of the different system input parameters is covered by at least one test case. Combinatorial test suite generation algorithms aim at producing a test suite covering all the required tuples in a small (possibly minimal) number of test cases, in order to reduce the cost of testing. The most used combinatorial technique is the pairwise testing (t = 2) which requires coverage of all pairs of input values. Constrained combinatorial testing takes also into account constraints over the system parameters, for instance forbidden tuples of inputs, modeling invalid or not realizable input values combinations. In this paper a new approach to combinatorial testing, tightly integrated with formal logic, is presented. In this approach, test predicates are used to formalize combinatorial testing as a logical problem, and an external formal logic tool is applied to solve it. Constraints over the input domain are expressed as logical predicates too, and effectively handled by the same tool. Moreover, inclusion or exclusion of select tuples is supported, allowing the user to customize the test suite layout. The proposed approach is supported by a prototype tool implementation and results of experimental assessment are also presented.     

On the complexity of distributed stable matching with small messages

We consider the distributed complexity of the stable matching problem (a.k.a. “stable marriage”). In this problem, the communication graph is undirected and bipartite, and each node ranks its neighbors. Given a matching of the nodes, a pair of unmatched nodes is called blocking if they prefer each other to their assigned match. A matching is called stable if it does not induce any blocking pair. In the distributed model, nodes exchange messages in each round over the communication links, until they find a stable matching. We show that if messages may contain at most B bits each, then any distributed algorithm that solves the stable matching problem requires ${\Omega(\sqrt{n/B\log n})}We consider the distributed complexity of the stable matching problem (a.k.a. “stable marriage”). In this problem, the communication graph is undirected and bipartite, and each node ranks its neighbors. Given a matching of the nodes, a pair of unmatched nodes is called blocking if they prefer each other to their assigned match. A matching is called stable if it does not induce any blocking pair. In the distributed model, nodes exchange messages in each round over the communication links, until they find a stable matching. We show that if messages may contain at most B bits each, then any distributed algorithm that solves the stable matching problem requires W(?{n/Blogn}){\Omega(\sqrt{n/B\log n})} communication rounds in the worst case, even for graphs of diameter O(log n), where n is the number of nodes in the graph. Furthermore, the lower bound holds even if we allow the output to contain O(?n){O(\sqrt n)} blocking pairs, and if a pair is considered blocking only if they like each other much more then their assigned match.     

Solving Connected Dominating Set Faster than 2<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>

In the connected dominating set problem we are given an n-node undirected graph, and we are asked to find a minimum cardinality connected subset S of nodes such that each node not in S is adjacent to some node in S. This problem is also equivalent to finding a spanning tree with maximum number of leaves. Despite its relevance in applications, the best known exact algorithm for the problem is the trivial Ω(2 ⁿ ) algorithm that enumerates all the subsets of nodes. This is not the case for the general (unconnected) version of the problem, for which much faster algorithms are available. Such a difference is not surprising, since connectivity is a global property, and non-local problems are typically much harder to solve exactly. In this paper we break the 2 ⁿ barrier, by presenting a simple O(1.9407 ⁿ ) algorithm for the connected dominating set problem. The algorithm makes use of new domination rules, and its analysis is based on the Measure and Conquer technique. An extended abstract of this paper appeared in the proceedings of FSTTCS’06. Fedor V. Fomin was additionally supported by the Research Council of Norway.     

Coalition formation for task allocation: theory and algorithms

This paper focuses on coalition formation for task allocation in both multi-agent and multi-robot domains. Two different problem formalizations are considered, one for multi-agent domains where agent resources are transferable and one for multi-robot domains. We demonstrate complexity theoretic differences between both models and show that, under both, the coalition formation problem, with m tasks, is NP-hard to both solve exactly and to approximate within a factor of O(m^1-e){O(m^{1-\epsilon})} for all ${\epsilon > 0}${\epsilon > 0}. Two natural restrictions of the coalition formation problem are considered. In the first situation agents are drawn from a set of j types. Agents of each type are indistinguishable from one another. For this situation a dynamic programming based approach is presented, which, for fixed j finds the optimal coalition structure in polynomial time and is applicable in both multi-agent and multi-robot domains. We then consider situations where coalitions are restricted to k or fewer agents. We present two different algorithms. Each guarantees the generated solution to be within a constant factor, for fixed k, of the optimal in terms of utility. Our algorithms complement Shehory and Kraus’ algorithm (Artif Intell 101(1–2):165–200, 1998), which provides guarantee’s on solution cost, as ours provides guarantees on utility. Our algorithm for general multi-agent domains is a modification of and has the same running time as Shehory and Kraus’ algorithm, while our approach for multi-robot domains runs in time O(n^\frac32m){O(n^{\frac{3}{2}}m)}, much faster than Vig and Adams (J Intell Robot Syst 50(1):85–118, 2007) modifications to Shehory and Kraus’ algorithm for multi-robot domains, which ran in time O(n ^k m), for n agents and m tasks.