Exploring the Relationship Between Max-Cut and Stable Set Relaxations

The max-cut and stable set problems are two fundamental -hard problems in combinatorial optimization. It has been known for a long time that any instance of the stable set problem can be easily transformed into a max-cut instance. Moreover, Laurent, Poljak, Rendl and others have shown that any convex set containing the cut polytope yields, via a suitable projection, a convex set containing the stable set polytope. We review this work, and then extend it in the following ways. We show that the rounded version of certain `positive semidefinite' inequalities for the cut polytope imply, via the same projection, a surprisingly large variety of strong valid inequalities for the stable set polytope. These include the clique, odd hole, odd antihole, web and antiweb inequalities, and various inequalities obtained from these via sequential lifting. We also examine a less general class of inequalities for the cut polytope, which we call odd clique inequalities, and show that they are, in general, much less useful for generating valid inequalities for the stable set polytope. As well as being of theoretical interest, these results have algorithmic implications. In particular, we obtain as a by-product a polynomial-time separation algorithm for a class of inequalities which includes all web inequalities.     

Composition of stable set polyhedra

Barahona and Mahjoub found a defining system of the stable set polytope for a graph with a cut-set of cardinality 2. We extend this result to cut-sets composed of a complete graph minus an edge and use the new theorem to derive a class of facets.     

Gelfand-Tsetlin polytopes and Feigin-Fourier-Littelmann-Vinberg polytopes as marked poset polytopes

Stanley (1986) showed how a finite partially ordered set gives rise to two polytopes, called the order polytope and chain polytope, which have the same Ehrhart polynomial despite being quite different combinatorially. We generalize his result to a wider family of polytopes constructed from a poset P with integers assigned to some of its elements.Through this construction, we explain combinatorially the relationship between the Gelfand-Tsetlin polytopes (1950) and the Feigin-Fourier-Littelmann-Vinberg polytopes (2010, 2005), which arise in the representation theory of the special linear Lie algebra. We then use the generalized Gelfand-Tsetlin polytopes of Berenstein and Zelevinsky (1989) to propose conjectural analogues of the Feigin-Fourier-Littelmann-Vinberg polytopes corresponding to the symplectic and odd orthogonal Lie algebras.     

The Hirsch Conjecture for the fractional stable set polytope

The edge formulation of the stable set problem is defined by two-variable constraints, one for each edge of a graph \(G\) , expressing the simple condition that two adjacent nodes cannot belong to a stable set. We study the fractional stable set polytope, i.e. the polytope defined by the linear relaxation of the edge formulation. Even if this polytope is a weak approximation of the stable set polytope, its simple geometrical structure provides deep theoretical insight as well as interesting algorithmic opportunities. Exploiting a graphic characterization of the bases, we first redefine pivots in terms of simple graphic operations, that turn a given basis into an adjacent one. These results lead us to prove that the combinatorial diameter of the fractional stable set polytope is at most the number of nodes of the given graph. As a corollary, the Hirsch bound holds for this class of polytopes.     

Canonical monotone decompositions of fractional stable matchings

This paper continues recent work that introduced algebraic methods for studying the stable marriage problem of Gale and Shapley [1962]. Vande Vate [1989] and Rothblum [1992] identified a set of linear inequalities which define a polytope whose extreme points correspond to the stable matchings. Points in this polytope are called fractional stable matchings. Here we identify a unique representation of fractional stable matchings as a convex combination of stable matchings that are arrangeable in a man-decreasing order. We refer to this representation and to a dual one, in terms of woman-decreasing order, as the canonical monotone representations. These representations can be interpreted as time-sharing stable matchings where particular stable matchings are used at each time-instance but the scheduled stable matchings are (occasionally) switched over time. The new representations allow us to extend, in a natural way, the lattice structure of the set of stable matchings to the set of all fractional stable matchings.     

Binary operations and lattice structure for a model of matching with contracts

We consider a restricted model of many-to-one matching with contracts and we order the set of stable allocations according both to the unanimous-for-doctors partial ordering and Blair’s partial ordering for hospitals. We define two binary operations to calculate the least upper bound and greatest lower bound for each pair of elements of this set in a simple way. By using these operations, we show that the set of stable allocations has dual lattice structures, thus reflecting an expected counterposition of interests between both sides of the market.     

Characterizing and bounding the imperfection ratio for some classes of graphs

Perfect graphs constitute a well-studied graph class with a rich structure, which is reflected by many characterizations with respect to different concepts. Perfect graphs are, for instance, precisely those graphs G where the stable set polytope STAB(G) equals the fractional stable set polytope QSTAB(G). The dilation ratio of the two polytopes yields the imperfection ratio of G. It is NP-hard to compute and, for most graph classes, it is even unknown whether it is bounded. For graphs G such that all facets of STAB(G) are rank constraints associated with antiwebs, we characterize the imperfection ratio and bound it by 3/2. Outgoing from this result, we characterize and bound the imperfection ratio for several graph classes, including near-bipartite graphs and their complements, namely quasi-line graphs, by means of induced antiwebs and webs, respectively.      

Stable Marriage and Genetic Algorithms: A Fertile Union

We describe a pair of genetic algorithms for solving two stable matching problems. Both stable matching problems we will consider involve a set of applicants for positions and a set of employers. Each applicant and each employer prepares a rank order list of a subset of the actors in the other set. The goal is to find an assignment of applicants to employers in which if applicant a is not assigned to employer b then either a prefers his assignment to b or b prefers its assignment toa . In other words, no applicant/employer pair can both improve their situations by dropping their current assignments in favor of each other. Our goal will be to enumerate the stable matchings. One of the problems we will consider is the well-known stable marriage problem, in which neither applicant nor employer preference lists are linked. In the other problem, we will allow pairs of applicants who form a couple to submit joint rank order lists of ordered pairs of employers.     

Order complex of ideals in a commutative ring with identity

Order complex is an important object associated to a partially ordered set. Following a suggestion from V. A. Vassiliev (1994), we investigate an order complex associated to the partially ordered set of nontrivial ideals in a commutative ring with identity. We determine the homotopy type of the geometric realization for the order complex associated to a general commutative ring with identity. We show that this complex is contractible except for semilocal rings with trivial Jacobson radical when it is homotopy equivalent to a sphere.     

Shellability of Interval Orders

An finite interval order is a partially ordered set whose elements are in correspondence with a finite set of intervals in the line, with disjoint intervals being ordered by their relative position. We show that any such order is shellable in the sense that its (not necessarily pure) order complex is shellable.     

Convex polytopes all of whose reverse lexicographic initial ideals are squarefree

A compressed polytope is an integral convex polytope any of whose reverse lexicographic initial ideals is squarefree. A sufficient condition for a -polytope to be compressed will be presented. One of its immediate consequences is that the class of compressed -polytopes includes (i) hypersimplices, (ii) order polytopes of finite partially ordered sets, and (iii) stable polytopes of perfect graphs.

     

Adjacency on the order polytope with applications to the theory of fuzzy measures

In this paper we study the adjacency structure of the order polytope of a poset. For a given poset, we determine whether two vertices in the corresponding order polytope are adjacent. This is done through filters in the original poset. We also prove that checking adjacency between two vertices can be done in quadratic time on the number of elements of the poset. As particular cases of order polytopes, we recover the adjacency structure of the set of fuzzy measures and obtain it for the set of p-symmetric measures for a given indifference partition; moreover, we show that the set of p-symmetric measures can be seen as the order polytope of a quotient set of the poset leading to fuzzy measures. From this property, we obtain the diameter of the set of p-symmetric measures. Finally, considering the set of p-symmetric measures as the order polytope of a direct product of chains, we obtain some other properties of these measures, as bounds on the volume and the number of vertices on certain cases.     

On the greedy dimension of a partial order

This paper introduces a new concept of dimension for partially ordered sets. Dushnik and Miller in 1941 introduced the concept of dimension of a partial order P, as the minimum cardinality of a realizer, (i.e., a set of linear extensions of P whose intersection is P). Every poset has a greedy realizer (i.e., a realizer consisting of greedy linear extensions). We begin the study of the notion of greedy dimension of a poset and its relationship with the usual dimension by proving that equality holds for a wide class of posets including N-free posets, two-dimensional posets and distributive lattices.     

Egalitarian solutions in the core

In this paper we define the Lorenz stable set, a subset of the core consisting of the allocations that are not Lorenz dominated by any other allocation of the core. We introduce the leximin stable allocation, which is derived from the application of the Rawlsian criterion on the core. We also define and axiomatize the egalitarian core, a set of core allocations for which no transfer from a rich player to a poor player is possible without violating the core restrictions. We find an inclusive relation of the leximin stable allocation and of the Lorenz stable set into the egalitarian core. Received: October 1999/Final version: July 2001