5 papers · 1 filter
On the Hardness of Scheduling With Non-Uniform Communication Delays
Sami Davies, Janardhan Kulkarni, Thomas Rothvoss +3
In the scheduling with non-uniform communication delay problem, the input is a set of jobs with precedence constraints. Associated with every precedence constraint between a pair o…
Almost Optimal Inapproximability of Multidimensional Packing Problems
Sai Sandeep
Multidimensional packing problems generalize the classical packing problems such as Bin Packing, Multiprocessor Scheduling by allowing the jobs to be -dimensional vectors. While…
Approximate Hypergraph Vertex Cover and generalized Tuza's conjecture
Venkatesan Guruswami, Sai Sandeep
A famous conjecture of Tuza states that the minimum number of edges needed to cover all the triangles in a graph is at most twice the maximum number of edge-disjoint triangles. Thi…
Minmax Regret for sink location on paths with general capacities
Mordecai Golin, Sai Sandeep
In dynamic flow networks, every vertex starts with items (flow) that need to be shipped to designated sinks. All edges have two associated quantities: length, the amount of time re…
PERMUTATION Strikes Back: The Power of Recourse in Online Metric Matching
Varun Gupta, Ravishankar Krishnaswamy, Sai Sandeep
In the classical Online Metric Matching problem, we are given a metric space with servers. A collection of clients arrive in an online fashion, and upon arrival, a client shoul…