A constrained matching problem: a polyhedral approach |
What people are saying - Write a review
We haven't found any reviews in the usual places.
Contents
A CONSTRAINED MATCHING PROBLEM | 25 |
COMPLEXITY OF CONSTRAINED MATCHING | 33 |
VALID INEQUALITIES | 41 |
6 other sections not shown
Common terms and phrases
argument augmenting path bipartite graph bundle Chapter Chvatal rank class of valid clause combinatorial optimization problems complete bipartite graph complete matching problem constrained assignment problem constrained matching problem conv(Sm convex combination convex hull cutting plane algorithm decision problems definition detecting violated dx _ dg entries Example facet of conv(S feasible solution G-matchable given graph G hamiltonian cycle hamiltonian path Hence i,n+j incidence matrix incidence vector inequalities define facets inequality for conv(S integer programming iteration Let G linear programming relaxation LP Itrs matching on G max flow max{cx nondeterministic algorithm Note NP-Complete NP-hard optimal solution permutation matrix polyhedral polyhedron polynomial time algorithm polytope Procedure 6.1 Proposition 5.1.1 scheduling periods separation problem separation procedure set partitioning problem shown in Figure solution to LP(B solvable in polynomial solved strong cutting plane tt(B valid inequality variables vertex vertices violated inequalities x e conv(S
Bibliographic information
| Title | A constrained matching problem: a polyhedral approach |
| Author | Ronny Aboudi |
| Publisher | Cornell University, January, 1986 |
| Original from | Cornell University |
| Digitized | Nov 30, 2010 |
| Length | 324 pages |
| Subjects | › Combinatorial analysis Matching theory Mathematics / Combinatorics |
| Export Citation | BiBTeX EndNote RefMan |