dimacs logo color

Events

Event Calendar

« Previous Month

August 2026

Next Month »
Sun Mon Tue Wed Thu Fri Sat
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

Seminar Details

Almost Optimal Inapproximability of Multidimensional Packing Problems

  • Start Date: February 9, 2022
  • Event Start Time: 11:00 AM
  • Event End Time: 12:00 PM
  • Seminar Series: Theoretical Computer Science Seminar
  • Presenter(s): Sai Sandeep - Carnegie Mellon University
  • Event Location: Online Event
  • Event Additional Info: <p>Special Note: The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar.&nbsp;</p> <p>See:&nbsp;<a href="https://theory.cs.rutgers.edu/theory_seminar" target="_blank">https://theory.cs.rutgers.edu/theory_seminar</a>&nbsp;</p>
  • Presentation Type: Stand Alone Presentation
  • Abstract:

    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 is available at https://arxiv.org/abs/2101.02854)