Computer Science Speaking Skills Talk / Theory Lunch
— 1:00pm
Location:
Virtual Presentation - ET
-
Remote Access - Zoom
Speaker:
SAI SANDEEP PALLERLA
,
Ph.D. Student
https://spallerl.github.io/
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.
Presented in Partial Fulfillment of the CSD Speaking Skills Requirement.
Zoom Participation. See announcement.
For More Information:
deb@cs.cmu.edu