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.     

Worst-case choice for the stable marriage problem

We present a worst-case choice for the stable marriage problem which takes the maximum number of stages for Gale and Shapely's algorithm (1962). We also analyze a coroutine solution recently suggested by Allison (1983) as well as a parallel algorithm for this problem.     

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     

Computational approaches to a combinatorial optimization problem arising from text classification

We present a combinatorial optimization problem with a particular cost structure: a constrained set of elements must be chosen from a ground set and the ground set is partitioned into subsets corresponding to types of elements. The constraints concern the elements, whereas the solution cost does not depend on the elements but only on their types. The motivation of this study comes from text categorization but we believe that the same combinatorial structure may emerge in many different contexts. We prove that the problem is NP-hard. We give a 0–1 linear programming formulation and we report on computational experiences on very large instances using branch-and-bound algorithms based on two different Lagrangean relaxations and heuristic algorithms based on Threshold Accepting and Simulated Annealing.     

Hardness results on the man-exchange stable marriage problem with short preference lists

We present two hardness results on the man-exchange stable marriage problem, one of which settles a recent conjecture of Irving on the complexity of determining whether a given instance of the stable marriage problem with short preference lists has a man-exchange stable matching.     

Physical mapping of chromosomes: A combinatorial problem in molecular biology

This paper is concerned wth the physical mapping of DNA molecules using data about the hybridization of oligonucleotide probes to a library of clones. In mathematical terms, the DNA molecule corresponds to an interval on the real line, each clone to a subinterval, and each probe occurs at a finite set of points within the interval. A stochastic model for the occurrences of the probes and the locations of the clones is assumed. Given a matrix of incidences between probes and clones, the task is to reconstruct the most likely interleaving of the clones. Combinatorial algorithms are presented for solving approximations to this problem, and computational results are presented.Research supported in part by NSF Grant No. CDA-9211106.Research supported in part by NSF Grant No. CCR-9005448.     

Stability of a combinatorial vector partition problem

The vector variant of the partition problem is considered. It is shown that the coincidence of the Pareto and Slater sets is the necessary and sufficient condition of stability of the problem with respect to its functional. __________ Translated from Kibernetika i Sistemny i Analiz, No. 3, pp. 177–181, May–June 2007.     

Postoptimal analysis of a vector minimax combinatorial problem

This paper considers a vector combinatorial problem with minimax criteria that provide the greatest uniformity of the parameters of efficient solutions. The necessary and sufficient conditions are obtained for five well-known types of stability of the problem against perturbations of parameters of the vector objective function.     

A combinatorial problem in the class of binary vectors of given weight

The notion of l-step is introduced in the class of binary vectors of given weight, which is a structural characteristic of a vector. Formulas for calculating the powers of sets of vectors of this class with certain structural properties related to the notion of l-step are derived.     

Sensitivity analysis of the classical transportation problem. A combinatorial approach

In this paper we discuss problems arising from variation of the original requirements, prices or both for some given transportation problem.Through the methods presented a considerable fraction of the new optimal variables is identified, provided that the new problem does not differ “too much” from the original one. This identification is achieved immediately once the given original basic variables are arranged in some simple sequences. Such sequences are already at our disposal when the original solution is obtained by the RSA method [2].It is shown how the results obtained may help determine the location and capacity of a proposed factory in an optimal fashion.     

A combinatorial auction improves school meals in Chile: a case of OR in developing countries

The Chilean State delivers essential meal services at schools for low‐income students. Junta Nacional de Auxilio Escolar y Becas, the institution in charge of covering 1,300,000 children, leases the meal service to private enterprises. We developed an integer linear programming model to assign the meal contracts, in a process known as combinatorial auctions. The resulting model, which is NP‐hard, led to significant improvements in efficiency and also contributed to making the process more transparent. The results are apparent in substantial improvements in quality and coverage of the service, and important savings to the country, which are equivalent to feeding 300,000 children in addition. We developed techniques to solve the combinatorial models and also to analyze and compare multiple scenarios to find robust solutions. For the objective function of this problem, we analyzed several options to consider different kinds of social benefits. In this paper, we describe the problem, the methodology and the results. We also present empirical results based on 6 years of experience. Finally, we discuss the relevance and impact of using operations research in these central issues in developing countries.     

A combinatorial optimization problem; optimal generalized cycle bases

A combinatorial optimization method is presented for selecting optimal generalized cycle bases corresponding to sparse flexibility matrices. A different technique based on a quasi-expansion process is developed which uses an intersection theorem for selecting independent elements for the bases.     

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.