Theory Lunch Seminar

  • Remote Access - Zoom
  • Virtual Presentation - ET
  • Ph.D. Student
  • Computer Science Department
  • Carnegie Mellon University

Almost Optimal Inapproximability of Multidimensional Packing Problems

Multidimensional packing problems generalize the standard packing problems such as Bin Packing, Multiprocessor Scheduling by allowing the jobs to be d-dimensional vectors. While the approximability of the scalar problems is well understood, there has been a significant gap between the approximation algorithms and the hardness results for the multidimensional variants. We close this gap by giving almost optimal inapproximability results for the multidimensional problems, namely, Vector Bin Packing, Vector Scheduling, and Vector Bin Covering.

For the Vector Bin Packing problem, our hardness result goes via the hardness of the set cover problem using a notion of packing dimension of set families. For the Vector Scheduling and Vector Bin Covering problems, we obtain our hardness results via variants of graph and hypergraph coloring problems.

Paper Reference

Zoom Participation. See announcement.

Theory Youtube Channel

For More Information, Please Contact: