On the approximability of the two-phase knapsack problem

DOI10.1007/S10878-019-00442-WzbMATH Open1433.90142OpenAlexW2966063667MaRDI QIDQ2279756FDOQ2279756

Authors: Kameng Nip, Zhenbo Wang 

Publication date: 13 December 2019

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-019-00442-w

Recommendations

• Approximation algorithms for a two-phase knapsack problem
• Publication:4952619
• An approximation scheme for the two-stage, two-dimensional knapsack problem
• A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
• Publication:4941826

zbMATH Keywords

approximation algorithmspolynomial-time approximation schememultiple knapsacktwo-phase knapsack

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Integer programming (90C10)

Cites Work

• Title not available (Why is that?)
• The design of approximation algorithms
• Title not available (Why is that?)
• An approximation algorithm for the generalized assignment problem
• Tight approximation algorithms for maximum separable assignment problems
• A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
• Bin packing can be solved within 1+epsilon in linear time
• Fast Approximation Algorithms for Knapsack Problems
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• A combination of flow shop scheduling and the shortest path problem
• Combination of two-machine flow shop scheduling and shortest path problems
• Combination of parallel machine scheduling and vertex cover
• Title not available (Why is that?)
• On two-stage stochastic knapsack problems
• Exact methods for the knapsack problem and its generalizations
• An Efficient Approximation Scheme for Variable-Sized Bin Packing
• A study on several combination problems of classic shop scheduling and shortest path
• Parameterized approximation scheme for the multiple knapsack problem
• Approximation schemes for knapsack problems with shelf divisions
• Technical Note—The Multiperiod Knapsack Problem
• Bounds for nested knapsack problems
• Single Machine Scheduling to Minimize Total Weighted Late Work
• Approximability of the two-stage stochastic knapsack problem with discretely distributed weights
• Packing groups of items into multiple knapsacks
• Combinations of some shop scheduling problems and the shortest path problem: complexity and approximation algorithms

Cited In (11)

• Faster Approximation Schemes for the Two-Dimensional Knapsack Problem
• A 2-APPROXIMATION ALGORITHM FOR THE MINIMUM KNAPSACK PROBLEM WITH A FORCING GRAPH
• Approximation Algorithms for a Bi-level Knapsack Problem
• Two-phases method and branch and bound procedures to solve the bi-objective knapsack problem
• Tight complexity bounds for the two-dimensional real knapsack problem
• Approximation algorithms for a two-phase knapsack problem
• Title not available (Why is that?)
• Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems
• On approximating the incremental knapsack problem
• On the multiperiod binary knapsack problem
• An approximation algorithm for solving unconstrained two-dimensional knapsack problems

This page was built for publication: On the approximability of the two-phase knapsack problem

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