A Lexicographic 0.5-Approximation Algorithm for the Multiple Knapsack Problem

DOI10.1134/S1990478918020072MaRDI QIDQ4558310zbMATH OpenOpenAlexFDO

Authors Alexander B. Khutoretsky, Sergey V. Bredikhin, A. A. Zamyatin

Publication date 21 November 2018

Published in Journal of Applied and Industrial Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1134/s1990478918020072

zbMATH Keywords

approximation algorithmapproximation ratiolexicographic orderingmultiple knapsack problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25)

Recommendations

• A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
• scientific article; zbMATH DE number 1418266
• An approximate algorithm for lexicographic search in multiple orders for the solution of the multidimensional Boolean knapsack problem
• A Fast Approximation Scheme for the Multiple Knapsack Problem
• A successive approximation algorithm for the multiple knapsack problem
• Parameterized approximation scheme for the multiple knapsack problem
• Parameterized approximation scheme for the multiple knapsack problem
• Approximability of two variants of multiple knapsack problems
• Approximation algorithms for the multiple knapsack problem with assignment restrictions
• Approximation for multi-knapsack problem

Cites work

• scientific article; zbMATH DE number 44282 (Why is no real title available?)
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• scientific article; zbMATH DE number 2107164 (Why is no real title available?)
• A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
• Discrete-variable extremum problems
• Parameterized approximation scheme for the multiple knapsack problem
• Truthful approximation mechanisms for restricted combinatorial auctions

Cited in

(2)

• An approximate algorithm for lexicographic search in multiple orders for the solution of the multidimensional Boolean knapsack problem
• Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems

This page was built for publication: A Lexicographic 0.5-Approximation Algorithm for the Multiple Knapsack Problem

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