A Lexicographic 0.5-Approximation Algorithm for the Multiple Knapsack Problem

DOI10.1134/S1990478918020072zbMath1413.68178OpenAlexW2805304733MaRDI QIDQ4558310

A. A. Zamyatin, Sergeĭ Vsevolodovich Bredikhin, A. Khutoretsky

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)

Related Items (1)

Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems

Cites Work

• Truthful approximation mechanisms for restricted combinatorial auctions
• Parameterized Approximation Scheme for the Multiple Knapsack Problem
• Discrete-Variable Extremum Problems
• A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
• Unnamed Item
• Unnamed Item
• Unnamed Item

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