Showing cs.DSShow all
3 papers · 1 filter
cs.DS2024
Improved linearly ordered colorings of hypergraphs via SDP rounding
Anand Louis, Alantha Newman, Arka Ray
We consider the problem of linearly ordered (LO) coloring of hypergraphs. A hypergraph has an LO coloring if there is a vertex coloring, using a set of ordered colors, so that (i)…
cs.DS2023
Improved Hardness of Approximation for Geometric Bin Packing
Arka Ray, Sai Sandeep
The Geometric Bin Packing (GBP) problem is a generalization of Bin Packing where the input is a set of -dimensional rectangles, and the goal is to pack them into unit -dimens…
cs.DS2022
Sparse Cuts in Hypergraphs from Random Walks on Simplicial Complexes
Anand Louis, Rameesh Paul, Arka Ray
There are a lot of recent works on generalizing the spectral theory of graphs and graph partitioning to hypergraphs. There have been two broad directions toward this goal. One gene…