Matching Problems with Additional Resource Constraints

Matchingprobleme mit zusätzlichen Ressourcenbeschränkungen

  • Matching problems with additional resource constraints are generalizations of the classical matching problem. The focus of this work is on matching problems with two types of additional resource constraints: The couple constrained matching problem and the level constrained matching problem. The first one is a matching problem which has imposed a set of additional equality constraints. Each constraint demands that for a given pair of edges either both edges are in the matching or none of them is in the matching. The second one is a matching problem which has imposed a single equality constraint. This constraint demands that an exact number of edges in the matching are so-called on-level edges. In a bipartite graph with fixed indices of the nodes, these are the edges with end-nodes that have the same index. As a central result concerning the couple constrained matching problem we prove that this problem is NP-hard, even on bipartite cycle graphs. Concerning the complexity of the level constrained perfect matching problem we show that it is polynomially equivalent to three other combinatorial optimization problems from the literature. For different combinations of fixed and variable parameters of one of these problems, the restricted perfect matching problem, we investigate their effect on the complexity of the problem. Further, the complexity of the assignment problem with an additional equality constraint is investigated. In a central part of this work we bring couple constraints into connection with a level constraint. We introduce the couple and level constrained matching problem with on-level couples, which is a matching problem with a special case of couple constraints together with a level constraint imposed on it. We prove that the decision version of this problem is NP-complete. This shows that the level constraint can be sufficient for making a polynomially solvable problem NP-hard when being imposed on that problem. This work also deals with the polyhedral structure of resource constrained matching problems. For the polytope corresponding to the relaxation of the level constrained perfect matching problem we develop a characterization of its non-integral vertices. We prove that for any given non-integral vertex of the polytope a corresponding inequality which separates this vertex from the convex hull of integral points can be found in polynomial time. Regarding the calculation of solutions of resource constrained matching problems, two new algorithms are presented. We develop a polynomial approximation algorithm for the level constrained matching problem on level graphs, which returns solutions whose size is at most one less than the size of an optimal solution. We then describe the Objective Branching Algorithm, a new algorithm for exactly solving the perfect matching problem with an additional equality constraint. The algorithm makes use of the fact that the weighted perfect matching problem without an additional side constraint is polynomially solvable. In the Appendix, experimental results of an implementation of the Objective Branching Algorithm are listed.
  • Matchingprobleme mit zusätzlichen Ressourcenbeschränkungen stellen eine Verallgemeinerung klassischer Matchingprobleme dar. Im Fokus dieser Arbeit stehen Matchingprobleme mit zwei Arten zusätzlicher Ressourcenbeschränkungen: Das couple constrained matching problem und das level constrained matching problem. Im couple constrained matching problem fordern die zusätzlichen Ressourcenbeschränkungen, dass für eine Menge von Kantenpaaren die Kanten eines Paares entweder beide im Matching sind oder beide nicht im Matching sind. Im level constrained matching problem kommt exakt eine zusätzliche Ressourcenbeschränkung vor. Sie gibt die Anzahl von sogenannten on-level Kanten in einem Matching vor. In einem bipartiten Graphen, dessen Knoten mit Index notiert sind, sind dies jene Kanten, deren zwei Endknoten den gleichen Index haben. Als zentrales Ergebnis zur Komplexität des couple constrained matching problem wird gezeigt, dass dieses Problem NP-schwer ist. Dies gilt auch dann, wenn es auf bipartite Kreisgraphen beschränkt wird. Ebenso werden Komplexitätsaspekte des level constrained matching problem betrachtet. Es werden drei kombinatorische Optimierungsprobleme aus der Literatur vorgestellt, die polynomiell äquivalent zum level constrained perfect matching problem sind. Anhand eines dieser drei Probleme, das restricted perfect matching problem, wird dargestellt, welchen Einfluss fixe und variable Parameter auf die Problemkomplexität haben können. Darüber hinaus steht besonders der Fall im Fokus, dass beide hier untersuchten Arten von Ressourcenbeschränkungen gemeinsam als zusätzliche Nebenbedingungen eines Matchingproblems auftreten. Diesbezüglich wird das couple and level constrained matching problem with on-level couples definiert. Dieses Matchingproblem enthält als zusätzliche Ressourcenbeschränkungen einen Spezialfall der couple constraints sowie eine level constraint. Mittels polynomieller Reduktion des Cliquenproblems wird gezeigt, dass die Entscheidungsversion dieses Problems NP-vollständig ist. Diesem Komplexitätsergebnis kommt eine besondere Bedeutung zu, da es zeigt, welchen Einfluss die level constraint auf eine polynomiell lösbare Variante eines ressourcenbeschränkten Matchingproblems haben kann. Ein weiterer Teil dieser Arbeit widmet sich den Polytopen von Matchingproblemen mit zusätzlichen Ressourcenbeschränkungen. Für das Polytop des relaxierten level constrained perfect matching problem wird eine Charakterisierung seiner nicht ganzzahligen Ecken erarbeitet. Es wird gezeigt, dass für jede nicht ganzzahlige Ecke in polynomiell vielen Schritten eine Ungleichung gefunden werden kann, die diese Ecke von der convexen Hülle der ganzzahligen Lösungen separiert. Zur Lösung ressourcenbeschränkter Matchingprobleme werden zwei neue Algorithmen entwickelt. Der erste Algorithmus ist ein Approximationsalgorithmus für das level constrained matching problem auf level Graphen. Die von ihm bestimmten Matchings erfüllen die level constraint und enthalten höchstens eine Kante weniger als eine Optimallösung. Der zweite Algorithmus ist der Objective Branching Algorithmus. Dieser löst perfekte Matchingprobleme mit zusätzlicher Gleichheitsnebenbedingung exakt. Er nutzt dabei aus, dass das gewichtete perfekte Matchingproblem ohne zusätzliche Ressourcenbeschränkung polynomiell lösbar ist. Experimentelle Ergebnisse einer Implementierung des Objective Branching Algorithmus finden sich im Anhang dieser Arbeit.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Dirk Johannes Thomas
URN:urn:nbn:de:hbz:385-9852
Advisor:Vries, Sven de Vries
Document Type:Doctoral Thesis
Language:English
Date of completion:2016/06/29
Publishing institution:Universität Trier
Granting institution:Universität Trier, Fachbereich 4
Date of final exam:2015/12/11
Release Date:2016/06/29
Tag:Combinatorial Optimization; Computational complexity; Couple constraints; Level constraints; Matching polytope
GND Keyword:Berechnungskomplexität; Graphentheorie; Kombinatorische Optimierung; Matching; Polyeder
Institutes:Fachbereich 4 / Mathematik
Dewey Decimal Classification:5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik
MSC-Classification:05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Cxx Graph theory (For applications of graphs, see 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15) / 05C70 Factorization, matching, partitioning, covering and packing
05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Cxx Graph theory (For applications of graphs, see 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15) / 05C85 Graph algorithms [See also 68R10, 68W05]
68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section {04 in that areag 68-00 General reference works (handbooks, dictionaries, bibliographies, etc.) / 68Qxx Theory of computing / 68Q25 Analysis of algorithms and problem complexity [See also 68W40]
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut

$Rev: 13581 $