Knapsack Cover Subject to a Matroid Constraint

DOI10.4230/LIPICS.FSTTCS.2013.275MaRDI QIDQ2963920zbMATH OpenOpenAlexFDO

Authors Venkatesan T. Chakaravarthy, Anamitra R. Choudhury, Sivaramakrishnan R. Natarajan, Sambuddha Roy

Publication date 21 February 2017

Full work available at URL https://doi.org/10.4230/LIPIcs.FSTTCS.2013.275

zbMATH Keywords

approximation algorithmsknapsack problemsLP roundingmatroid constraints

Mathematics Subject Classification ID

Approximation algorithms (68W25) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Multi-constrained matroidal knapsack problems
• Lifting the knapsack cover inequalities for the knapsack polytope
• The matroidal knapsack: A class of (often) well-solvable problems
• The Integer Knapsack Cover Polyhedron
• Supermodular covering knapsack polytope
• On separating cover inequalities for the multidimensional knapsack problem
• Multi-cover inequalities for totally-ordered multiple knapsack sets
• Lifting for the integer knapsack cover polyhedron
• Knapsack polytopes: a survey
• Matroid-constrained vertex cover

Cited in

(4)

• Multi-constrained matroidal knapsack problems
• The Integer Knapsack Cover Polyhedron
• scientific article; zbMATH DE number 847586 (Why is no real title available?)
• Minimal covers, minimal sets and canonical facets of the posynomial knapsack polytope

This page was built for publication: Knapsack Cover Subject to a Matroid Constraint

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2963920)