Progress in Combinatorial OptimizationWilliam R. Pulleyblank |
From inside the book
Results 1-3 of 29
Page 318
William R. Pulleyblank. The system Ax ≤ b is called box totally dual integral or box t.d.i. if the system " Ax ≤ b , c ≤ x ≤ d " is t.d.i. for all vectors c , d . It is not difficult to see that box total dual integrality implies ...
William R. Pulleyblank. The system Ax ≤ b is called box totally dual integral or box t.d.i. if the system " Ax ≤ b , c ≤ x ≤ d " is t.d.i. for all vectors c , d . It is not difficult to see that box total dual integrality implies ...
Page 334
... box totally dual integral . It was proved earlier by Cunningham [ 1977 ] and McDiarmid [ 1978 ] that for integer fi ... box total dual integrality of ( 48 ) can be derived from that of ( 41 ) ( Frank and Tardos [ 1982 ] ) . Indeed , let ...
... box totally dual integral . It was proved earlier by Cunningham [ 1977 ] and McDiarmid [ 1978 ] that for integer fi ... box total dual integrality of ( 48 ) can be derived from that of ( 41 ) ( Frank and Tardos [ 1982 ] ) . Indeed , let ...
Page 336
... box totally dual integral . ( V ' € C ) ( 55 ) This scheme clearly contains König's theorems ( 1 ) , the Lucchesi- Younger theorem ( IX ) and the box total dual integrality of ( 24 ) and ( 25 ) , the matroid and polymatroid intersection ...
... box totally dual integral . ( V ' € C ) ( 55 ) This scheme clearly contains König's theorems ( 1 ) , the Lucchesi- Younger theorem ( IX ) and the box total dual integrality of ( 24 ) and ( 25 ) , the matroid and polymatroid intersection ...
Contents
Lifting the Facets of Polyhedra | 3 |
Partitioning Spectra and Linear Programming 113 | 13 |
Oriented Matroids and Triangulations of Convex Polytopes 22 | 27 |
Copyright | |
16 other sections not shown
Other editions - View all
Common terms and phrases
adjacent apply arcs arrow B₁ basic Meyniel graph bipartite graph bisimplicial box totally dual C₁ chain circuit clique cocircuit columns combinatorial optimization Computer connected components contains convex corresponding crossing family decomposition defined denote digraph directed graph disjoint dynamic graph edges Edmonds element ellipsoid method equivalent eulerian path exists facet feasible G(V₁ G₁ G₂ given graph G greedoid greedy algorithm Hence implies induced induced subgraph inequalities intersecting interval order K₁ lattice LEMMA Let G linear program linear system Lovász machines matching Math Mathematical matrix maximal maximum minimal network flow node NP-complete obtain oriented matroid pairs partial order partially ordered set partition path perfect graphs points polyhedra polyhedron polymatroid polynomial polytope proof result satisfies schedule Schrijver solve structure subgraph submodular function subsets supermodular theorem theory tion total dual integrality U₁ V₁ vector vertex vertices x₁ y₁