\(O(n \log n)\) procedures for tightening cover inequalities
type: Item
instance of: scholarly article
title: \(O(n \log n)\) procedures for tightening cover inequalities
zbMATH Open document ID: 0941.90056
DOI: 10.1016/S0377-2217(98)00100-3
published in: European Journal of Operational Research
publication date: 1999-11-28T00:00:00Z
Mathematics Subject Classification ID: 90C09
Mathematics Subject Classification ID: 90C60
zbMATH DE Number: 1371073
zbMATH Keywords: 0-1 program
zbMATH Keywords: cover
zbMATH Keywords: clique
zbMATH Keywords: probing
zbMATH Keywords: knapsack constraint
zbMATH Keywords: coefficient increase
zbMATH Keywords: lifting
author: Laureano F. Escudero Bueno
author: A. Garin
author: Gloria Pérez
MaRDI profile type: Publication
cites work: Facets of the Knapsack Polytope From Minimal Covers
cites work: Analysis of mathematical programming problems prior to applying the simplex algorithm
cites work: Solving Large-Scale Zero-One Linear Programming Problems
cites work: On tightening cover induced inequalities
cites work: Efficient reformulation for 0-1 programs -- methods and computational results
cites work: \(O(n)\) procedures for identifying maximal cliques and non-dominated extensions of consecutive minimal covers and alternates
cites work: On the Dietrich-Escudero approach for solving the \(0-1\) knapsack problem with a \(0-1\) objective function
cites work: A framework for tightening 0–1 programs based on extensions of pure 0–1 KP and SS problems
cites work: Sequence independent lifting of cover inequalities
cites work: Logical Reduction Methods in Zero-One Programming—Minimal Preferred Variables
cites work: Improving LP-Representations of Zero-One Linear Programs for Branch-and-Cut
cites work: Properties of vertex packing and independence system polyhedra
cites work: Lifted cover facets of the 0-1 knapsack polytope with GUB constraints
cites work: Q4040221
cites work: On the facial structure of set packing polyhedra
cites work: Technical Note—A Note on Zero-One Programming
cites work: Preprocessing and Probing Techniques for Mixed Integer Programming Problems
cites work: Solving Mixed Integer Programming Problems Using Automatic Reformulation
cites work: Strong formulations for mixed integer programming: A survey
cites work: Easily Computable Facets of the Knapsack Polytope
full work available at URL: s0377-2217(98)00100-3
OpenAlex ID: W2012987521
Recommended article: Tight bounds on subexponential time approximation of set cover and related problems
Recommended article: Q4228484
Recommended article: Tight approximation bounds for combinatorial frugal coverage algorithms
Recommended article: A Technique for Lower Bounding the Cover Time
Recommended article: The complexity of cover inequality separation
Recommended article: Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k-Coverage, Unique Set Cover and Related Problems (via t-Wise Agreement Testing Theorem)
Recommended article: Tight Approximation Bounds for Greedy Frugal Coverage Algorithms
Recommended article: Q4796708
Recommended article: An Approximation Algorithm for Minimum Convex Cover with Logarithmic Performance Guarantee
Recommended article: A \(\Theta (\log n)\)-approximation for the set cover problem with set ownership
description: scientific article; zbMATH DE number 1371073