Optimization Online


Stable Multi-Sets

Arie M.C.A. Koster (koster***at***zib.de)
Adrian Zymolka (zymolka***at***zib.de)

Abstract: In this paper we introduce a generalization of stable sets: stable multi-sets. A stable multi-set is an assignment of integers to the vertices of a graph, such that specified bounds on vertices and edges are not exceeded. In case all vertex and edge bounds equal one, stable multi-sets are equivalent to stable sets. For the stable multi-set problem, we derive reduction rules and study the associated polytope. We state necessary and sufficient conditions for the extreme points of the linear relaxation to be integer. These conditions generalize the conditions for the stable set polytope. Moreover, the classes of odd cycle and clique inequalities for stable sets are generalized to stable multi-sets and conditions for them to be facet defining are determined. The study of stable multi-sets is initiated by optimization problems in the field of telecommunication networks. Stable multi-sets emerge as an important substructure in the design of optical networks.

Keywords: stable multi-sets, polyhedral combinatorics

Category 1: Combinatorial Optimization (Polyhedra )

Category 2: Combinatorial Optimization (Graphs and Matroids )

Citation: updated version of ZIB-Report 00-36, Konrad-Zuse-Zentrum f�r Informationstechnik Berlin (ZIB), December 2000. Revised version published in Mathematical Methods of Operations Research 56 (1), 2002, pp. 45-65.

Download: [Postscript]

Entry Submitted: 02/15/2001
Entry Accepted: 02/15/2001
Entry Last Modified: 10/04/2002

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society