Knapsack problem with objective value gaps
From MaRDI portal
Publication:2361124
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
computational complexity; knapsack problem; fully polynomial time approximation scheme; forbidden values
90C27: Combinatorial optimization
Related Items
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