We study a fundamental fair allocation problem, where the agent’s value is determined by the number of bins either used to pack or cover the items allocated to them. Fairness is evaluated using the maximin share (MMS) criterion. This problem is not only motivated by practical applications, but also serves as a natural framework for studying group fairness. As MMS is not always satisfiable, we consider two types of approximations: cardinal and ordinal. For cardinal approximation, we relax the requirements of being packed or covered for a bin, and for ordinal approximation, we relax the number of bins that are packed or covered. For all models of interest, we provide constant approximation algorithms.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Bin Packing and Covering: Pushing the Frontier on the Maximin Share Fairness

  • Bo Li,
  • Ankang Sun,
  • Zunyu Wang,
  • Yu Zhou

摘要

We study a fundamental fair allocation problem, where the agent’s value is determined by the number of bins either used to pack or cover the items allocated to them. Fairness is evaluated using the maximin share (MMS) criterion. This problem is not only motivated by practical applications, but also serves as a natural framework for studying group fairness. As MMS is not always satisfiable, we consider two types of approximations: cardinal and ordinal. For cardinal approximation, we relax the requirements of being packed or covered for a bin, and for ordinal approximation, we relax the number of bins that are packed or covered. For all models of interest, we provide constant approximation algorithms.