Showing cs.CCShow all
3 papers · 1 filter
cs.CC2022
Some Results on Approximability of Minimum Sum Vertex Cover
Aleksa Stanković
We study the Minimum Sum Vertex Cover problem, which asks for an ordering of vertices in a graph that minimizes the total cover time of edges. In particular, n vertices of the grap…
cs.CC2020
On Regularity of Max-CSPs and Min-CSPs
Aleksa Stankovic
We study approximability of regular constraint satisfaction problems, i.e., CSPs where each variable in an instance has the same number of occurrences. In particular, we show that…
cs.CC2019
Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder
Per Austrin, Aleksa Stankovic
Assuming the Unique Games Conjecture, we show that existing approximation algorithms for some Boolean Max-2-CSPs with cardinality constraints are optimal. In particular, we prove t…