Properties of vertex packing and independence system polyhedra

DOI10.1007/BF01580222zbMath0281.90072OpenAlexW2075339720MaRDI QIDQ4766816

Nemhauser, George I., Leslie E. jun. Trotter

Publication date: 1974

Published in: Mathematical Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01580222

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35) Integer programming (90C10)

Related Items (only showing first 100 items - show all)

More complete intersection theorems ⋮ Vertex packing problem application to the design of electronic testing fixtures ⋮ A Faster Parameterized Algorithm for Group Feedback Edge Set ⋮ A capacitated hub location problem under hose demand uncertainty ⋮ Valid inequalities and facets for a hypergraph model of the nonlinear knapsack and the FMS part selection problems ⋮ Fixed interval scheduling: models, applications, computational complexity and algorithms ⋮ New facets for the two-stage uncapacitated facility location polytope ⋮ Improved formulations and branch-and-cut algorithms for the angular constrained minimum spanning tree problem ⋮ Alternative formulations for the set packing problem and their application to the winner determination problem ⋮ Complexity of searching an immobile hider in a graph ⋮ On ternary problems ⋮ On the set covering polytope. I: All the facets with coefficients in \(\{\) 0,1,2\(\}\) ⋮ On the 0,1 facets of the set covering polytope ⋮ A generalization of antiwebs to independence systems and their canonical facets ⋮ On the facial structure of the set covering polytope ⋮ On cutting-plane proofs in combinatorial optimization ⋮ Sparse obstructions for minor-covering parameters ⋮ Facets and lifting procedures for the set covering polytope ⋮ The stable set problem: clique and nodal inequalities revisited ⋮ \(O(n \log n)\) procedures for tightening cover inequalities ⋮ Solving a Multigroup Mixed-Integer Programming-Based Constrained Discrimination Model ⋮ Complementation in T-perfect graphs ⋮ Strong formulation for the spot 5 daily photograph scheduling problem ⋮ On the complete set packing and set partitioning polytopes: properties and rank 1 facets ⋮ On certain polytopes associated with graphs ⋮ The stable set polytope of claw-free graphs with stability number at least four. I. Fuzzy antihat graphs are \(\mathcal{W}\)-perfect ⋮ On fractional realizations of graph degree sequences ⋮ On the 2-Club Polytope of Graphs ⋮ Polytope des independants d'un graphe série-parallèle ⋮ Complexity of branch-and-bound and cutting planes in mixed-integer optimization ⋮ Discrete extremal problems ⋮ 2-clique-bond of stable set polyhedra ⋮ On stable set polyhedra for K//(1,3)free graphs ⋮ Vertex packings: Structural properties and algorithms ⋮ Faces for a linear inequality in 0–1 variables ⋮ Facet of regular 0–1 polytopes ⋮ On the facets of lift-and-project relaxations under graph operations ⋮ Adding incompatibilities to the simple plant location problem: formulation, facets and computational experience ⋮ Facets of the knapsack polytope ⋮ Handelman's hierarchy for the maximum stable set problem ⋮ The symmetric traveling salesman polytope and its graphical relaxation: Composition of valid inequalities ⋮ Typical performance of approximation algorithms for NP-hard problems ⋮ Fixed cardinality stable sets ⋮ Cutting planes from extended LP formulations ⋮ Crown reductions for the minimum weighted vertex cover problem ⋮ Valid inequalities for a single constrained 0-1 MIP set intersected with a conflict graph ⋮ On the mixed set covering, packing and partitioning polytope ⋮ On tightening cover induced inequalities ⋮ The generalized independent set problem: polyhedral analysis and solution approaches ⋮ The complexity of lifted inequalities for the knapsack problem ⋮ Efficient stabilization of cooperative matching games ⋮ The strength of Dantzig-Wolfe reformulations for the stable set and related problems ⋮ Further facet generating procedures for vertex packing polytopes ⋮ Polyhedral results for the precedence-constrained knapsack problem ⋮ Cutting planes in integer and mixed integer programming ⋮ A class of facet producing graphs for vertex packing polyhedra ⋮ A polyhedral study of the generalized vertex packing problem ⋮ On \(f\)-domination: polyhedral and algorithmic results ⋮ Polyhedral properties of the induced cluster subgraphs ⋮ Lifting the facets of zero–one polytopes ⋮ Hitting Forbidden Minors: Approximation and Kernelization ⋮ On the set covering polytope. II: Lifting the facets with coefficients in \(\{\) 0,1,2\(\}\) ⋮ (1,k)-configurations and facets for packing problems ⋮ Approximability of clique transversal in perfect graphs ⋮ Optimizing over pure stationary equilibria in consensus stopping games ⋮ Ehrhart series of fractional stable set polytopes of finite graphs ⋮ Extended formulations for vertex cover ⋮ Optimization algorithms for the disjunctively constrained knapsack problem ⋮ Gear composition and the stable set polytope ⋮ Minimum partition of an independence system into independent sets ⋮ Valid inequalities and facets of the capacitated plant location problem ⋮ Single machine precedence constrained scheduling is a Vertex cover problem ⋮ An \(O(n \log n)\) procedure for identifying facets of the knapsack polytope. ⋮ Fractional matroid matchings ⋮ Matchings and covers in hypergraphs ⋮ A polynomial algorithm for maximum weighted vertex packings on graphs without long odd cycles ⋮ The unsuitable neighbourhood inequalities for the fixed cardinality stable set polytope ⋮ Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics ⋮ Minimal covers, minimal sets and canonical facets of the posynomial knapsack polytope ⋮ Facets and algorithms for capacitated lot sizing ⋮ Valid inequalities, cutting planes and integrality of the knapsack polytope ⋮ Strong and weak edges of a graph and linkages with the vertex cover problem ⋮ A New Facet Generating Procedure for the Stable Set Polytope ⋮ Stable sets, corner polyhedra and the Chvàtal closure ⋮ A new lifting theorem for vertex packing ⋮ A polyhedral approach to sequence alignment problems ⋮ Tractability of König edge deletion problems ⋮ Worst-case analysis of clique MIPs ⋮ On the facets of the simple plant location packing polytope ⋮ Dynamic node packing ⋮ On certain classes of fractional matchings ⋮ Nearly optimal robust secret sharing against rushing adversaries ⋮ The complexity of facets (and some facets of complexity) ⋮ Some facets of the simple plant location polytope ⋮ Erratum to ``Comparison of column generation models for channel assignment in cellular networks ⋮ The maximum clique problem ⋮ Uncapacitated Euclidean hub location: strengthened formulation, new facets and a relax-and-cut algorithm ⋮ A cutting plane method for solving harvest scheduling models with area restrictions ⋮ Extended formulations for stable set polytopes of graphs without two disjoint odd cycles ⋮ Light on the infinite group relaxation. I: Foundations and taxonomy

Cites Work

This page was built for publication: Properties of vertex packing and independence system polyhedra