Amatya Sharma

collaborators

3 papers

cs.DS2025

Min-CSPs on Complete Instances II: Polylogarithmic Approximation for Min-NAE-3-SAT

Aditya Anand, Euiwoong Lee, Davide Mazzali +1

This paper studies complete $k$ -Constraint Satisfaction Problems (CSPs), where an $n$ -variable instance has exactly one nontrivial constraint for each subset of $k$ variables, i.e.…

cs.DS2024

Min-CSPs on Complete Instances

Aditya Anand, Euiwoong Lee, Amatya Sharma

Given a fixed arity $k \geq 2$ , Min- $k$ -CSP on complete instances involves a set of $n$ variables $V$ and one nontrivial constraint for every $k$ -subset of variables (so there are…

cs.DS2024

A Decomposition Approach to the Weighted $k$ -server Problem

Nikhil Ayyadevara, Ashish Chiplunkar, Amatya Sharma

A natural variant of the classical online $k$ -server problem is the Weighted $k$ -server problem, where the cost of moving a server is its weight times the distance through which it…

Min-CSPs on Complete Instances II: Polylogarithmic Approximation for Min-NAE-3-SAT

Min-CSPs on Complete Instances

A Decomposition Approach to the Weighted k-server Problem

A Decomposition Approach to the Weighted $k$ -server Problem