Showing cs.DSShow all
3 papers · 1 filter
cs.DS2025
SDPs and Robust Satisfiability of Promise CSP
Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep
For a constraint satisfaction problem (CSP), a robust satisfaction algorithm is one that outputs an assignment satisfying most of the constraints on instances that are near-satisfi…
cs.DS2025
Minmax-Regret -Sink Location on a Dynamic Tree Network with Uniform Capacities
Mordecai J. Golin, Sai Sandeep
A dynamic flow network with uniform capacity is a graph in which at most units of flow can enter an edge in one time unit. If flow enters a vertex faster than it can le…
cs.DS2025
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…