Knapsack problem with objective value gaps

DOI10.1007/s11590-016-1043-3zbMath1373.90127MaRDI QIDQ2361124

Mikhail Y. Kovalyov, Alain Quilliot, Alexandre Dolgui

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 complexity; knapsack problem; fully polynomial time approximation scheme; forbidden values

Mathematics Subject Classification ID

90C27: Combinatorial optimization

Related Items

Simple paths with exact and forbidden lengths

Cites Work

• Unnamed Item
• Unnamed Item
• A provably tight delay-driven concurrently congestion mitigating global routing algorithm
• Exact arborescences, matchings and cycles
• A new fully polynomial time approximation scheme for the Knapsack problem
• Approximation algorithms for \(k\)-partitioning problems with partition matroid constraint
• The shortest route problem with constraints
• The Exact Weighted Independent Set Problem in Perfect Graphs and Related Classes
• An <sc>fptas</sc> for Response Time Analysis of Fixed Priority Real-Time Tasks with Resource Augmentation
• The complexity of restricted spanning tree problems
• Approximation Schemes for the Restricted Shortest Path Problem
• Combinatorial Problems: Reductibility and Approximation
• Combinatorial Problems: Reductibility and Approximation
• Maximum matching of given weight in complete and complete bipartite graphs
• Finding, minimizing, and counting weighted subgraphs
• Exact Weight Subgraphs and the k-Sum Conjecture
• A Computationally Efficient FPTAS for Convex Stochastic Dynamic Programs