Parametric packing of selfish items and the subset sum algorithm

DOI10.1007/s00453-014-9942-0zbMath1394.68440OpenAlexW2568989686WikidataQ105583372 ScholiaQ105583372MaRDI QIDQ261356

Julián Mestre, Elena Kleiman, Leah Epstein

Publication date: 23 March 2016

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-014-9942-0

zbMATH Keywords

game theoryapproximation algorithmsbin packingprice of anarchyalgorithm theory

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25) Combinatorial games (91A46)

Related Items (15)

Selfish Vector Packing ⋮ A note on a selfish bin packing problem ⋮ Pareto optimal equilibria for selfish bin packing with uniform cost sharing ⋮ Using weight decision for decreasing the price of anarchy in selfish bin packing games ⋮ Online variable-sized bin packing with conflicts ⋮ Bin packing game with a price of anarchy of \(\frac{3}{2}\) ⋮ Quality of equilibria for selfish bin packing with cost sharing variants ⋮ A bin packing game with cardinality constraints under the best cost rule ⋮ Selfish vector packing ⋮ The intermediate price of anarchy (IPoA) in bin packing games ⋮ A new lower bound on the price of anarchy of selfish bin packing ⋮ An improved mechanism for selfish bin packing ⋮ Quality of strong equilibria for selfish bin packing with uniform cost sharing ⋮ From packing rules to cost-sharing mechanisms ⋮ On the sequential price of anarchy of isolation games

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Selfish bin packing
• The price of selfish routing
• Strong price of anarchy
• Modified subset sum heuristics for bin packing
• Worst-case analysis of the subset sum algorithm for bin packing.
• Tight bounds for worst-case equilibria
• How bad is selfish routing?
• Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP
• A simple on-line bin-packing algorithm
• Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
• Reducibility among Combinatorial Problems
• Strong Price of Anarchy for Machine Load Balancing
• STACS 2005

This page was built for publication: Parametric packing of selfish items and the subset sum algorithm