O(n n) procedures for tightening cover inequalities
From MaRDI portal
Publication:1124826
Recommendations
- Tight bounds on subexponential time approximation of set cover and related problems
- scientific article; zbMATH DE number 1256748
- Tight approximation bounds for combinatorial frugal coverage algorithms
- A Technique for Lower Bounding the Cover Time
- The complexity of cover inequality separation
- Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k-Coverage, Unique Set Cover and Related Problems (via t-Wise Agreement Testing Theorem)
- Tight approximation bounds for greedy frugal coverage algorithms
- scientific article; zbMATH DE number 1877049
- An Approximation Algorithm for Minimum Convex Cover with Logarithmic Performance Guarantee
- A \(\Theta (\log n)\)-approximation for the set cover problem with set ownership
Cites work
- \(O(n)\) procedures for identifying maximal cliques and non-dominated extensions of consecutive minimal covers and alternates
- A framework for tightening 0-1 programs based on extensions of pure 0-1 KP and SS problems
- Analysis of mathematical programming problems prior to applying the simplex algorithm
- Easily Computable Facets of the Knapsack Polytope
- Efficient reformulation for 0-1 programs -- methods and computational results
- Facets of the Knapsack Polytope From Minimal Covers
- scientific article; zbMATH DE number 193411 (Why is no real title available?)
- Improving LP-Representations of Zero-One Linear Programs for Branch-and-Cut
- Lifted cover facets of the 0-1 knapsack polytope with GUB constraints
- Logical Reduction Methods in Zero-One Programming—Minimal Preferred Variables
- On the Dietrich-Escudero approach for solving the \(0-1\) knapsack problem with a \(0-1\) objective function
- On the facial structure of set packing polyhedra
- On tightening cover induced inequalities
- Preprocessing and Probing Techniques for Mixed Integer Programming Problems
- Properties of vertex packing and independence system polyhedra
- Sequence independent lifting of cover inequalities
- Solving Large-Scale Zero-One Linear Programming Problems
- Solving Mixed Integer Programming Problems Using Automatic Reformulation
- Strong formulations for mixed integer programming: A survey
- Technical Note—A Note on Zero-One Programming
Cited in
(15)- On tightening cover induced inequalities
- On tightening 0-1 programs based on extensions of pure 0-1 knapsack and subset-sum problems
- On using an automatic scheme for obtaining the convex hull defining inequalities of a Weismantel 0-1 knapsack constraint
- Obtaining clique, cover and coefficient reduction inequalities as Chvatal-Gomory inequalities and Gomory fractional cuts
- Partial cover and complete cover inequalities
- An \(O(n \log n)\) procedure for identifying facets of the knapsack polytope.
- A correction of the justification of the Dietrich-Escudero-Garín-Pérez O(n) procedures for identifying maximal cliques and non-dominated extensions of consecutive minimal covers and alternates
- New Procedures For Preprocessing 0–1 Models With Knapsack-Like Constraints And Conjunctive And/Or Disjunctive Variable Upper Bounds
- Nonlinear 0–1 programming: II. Dominance relations and algorithms
- scientific article; zbMATH DE number 2108946 (Why is no real title available?)
- A framework for tightening 0-1 programs based on extensions of pure 0-1 KP and SS problems
- Approximate and exact merging of knapsack constraints with cover inequalities
- A note for tightening 0-1 models
- Second-order cover inequalities
- Higher-order cover cuts from zero-one knapsack constraints augmented by two-sided bounding inequalities
This page was built for publication: \(O(n \log n)\) procedures for tightening cover inequalities
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1124826)
