Knapsack problem with objective value gaps

DOI10.1007/S11590-016-1043-3MaRDI QIDQ2361124zbMATH OpenOpenAlexFDO

Authors M. Y. Kovalyov, Alexandre Dolgui, Alain Quilliot

Publication date 29 June 2017

Published in Optimization Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11590-016-1043-3

zbMATH Keywords

computational complexityknapsack problemfully polynomial time approximation schemeforbidden values

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• Integrality gaps of integer knapsack problems
• A nonlinear knapsack problem
• Approximation issues of fractional knapsack with penalties: a note
• scientific article; zbMATH DE number 1302173
• Approximation for knapsack problems with multiple constraints

Cites work

• scientific article; zbMATH DE number 44282 (Why is no real title available?)
• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• A computationally efficient FPTAS for convex stochastic dynamic programs
• A new fully polynomial time approximation scheme for the Knapsack problem
• A provably tight delay-driven concurrently congestion mitigating global routing algorithm
• An <sc>fptas</sc> for Response Time Analysis of Fixed Priority Real-Time Tasks with Resource Augmentation
• Approximation Schemes for the Restricted Shortest Path Problem
• Approximation algorithms for \(k\)-partitioning problems with partition matroid constraint
• Combinatorial Problems: Reductibility and Approximation
• Combinatorial Problems: Reductibility and Approximation
• Exact arborescences, matchings and cycles
• Exact weight subgraphs and the \(k\)-sum conjecture
• Finding, minimizing, and counting weighted subgraphs
• Maximum matching of given weight in complete and complete bipartite graphs
• The complexity of restricted spanning tree problems
• The exact weighted independent set problem in perfect graphs and related classes
• The shortest route problem with constraints

Cited in

(2)

• Simple paths with exact and forbidden lengths
• Integrality gaps of integer knapsack problems

This page was built for publication: Knapsack problem with objective value gaps

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