2026-07-23T20:31:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19322 2024-03-06T11:03:46Z ddc:004 open_access

Improved Approximation for Two-Dimensional Vector Multiple Knapsack Cohen, Tomer Kulik, Ariel Shachnai, Hadas vector multiple knapsack two-dimensional packing randomized rounding approximation algorithms We study the uniform 2-dimensional vector multiple knapsack (2VMK) problem, a natural variant of multiple knapsack arising in real-world applications such as virtual machine placement. The input for 2VMK is a set of items, each associated with a 2-dimensional weight vector and a positive profit, along with m 2-dimensional bins of uniform (unit) capacity in each dimension. The goal is to find an assignment of a subset of the items to the bins, such that the total weight of items assigned to a single bin is at most one in each dimension, and the total profit is maximized. Our main result is a (1 - (ln 2)/2 - ε)-approximation algorithm for 2VMK, for every fixed ε > 0, thus improving the best known ratio of (1 - 1/e - ε) which follows as a special case from a result of [Fleischer at al., MOR 2011]. Our algorithm relies on an adaptation of the Round&Approx framework of [Bansal et al., SICOMP 2010], originally designed for set covering problems, to maximization problems. The algorithm uses randomized rounding of a configuration-LP solution to assign items to ≈ m⋅ln 2 ≈ 0.693⋅m of the bins, followed by a reduction to the (1-dimensional) Multiple Knapsack problem for assigning items to the remaining bins. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tomer Cohen and Ariel Kulik and Hadas Shachnai 2023 Is Part Of LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2023.20 urn:nbn:de:0030-drops-193229 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.20 eng https://creativecommons.org/licenses/by/4.0/legalcode