Knapsack

Characterization of Knapsack Polytopes using Minimal Cover Inequalities

  • Shreyas Bhowmik
  • Guneshwar Anand
  • Sachin Jayaswal
    • Categories 0-1 Programming Tags , , ,

    In this paper, we compare the strength of alternate formulations (polyhedra) of the binary knapsack set. We introduce a specific class of knapsack sets for which we prove that the polyhedra based on their minimal cover inequalities (together with the bounds on the variables) are strictly contained inside the polyhedra defined by their continuous knapsack … Read more

    Greedy Algorithms with Imprecise Oracles for Submodular Knapsack Problems

  • Sabine Münch
    • Categories Approximation Algorithms, Combinatorial Optimization Tags , , ,

    We consider the problem of maximizing a monotone increasing, normalized, and submodular function defined on a set of weighted items under a knapsack constraint. A well-known greedy algorithm, analyzed by Wolsey (1982), achieves an approximation factor of \(0.357\) for this problem. This greedy algorithm starts with an empty solution set and iteratively generates a feasible … Read more