3 citations · 3 across the 1 of their papers we have counts for
4 papers
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…
Max-3-Lin over Non-Abelian Groups with Universal Factor Graphs
Amey Bhangale, Aleksa Stankovic
Factor graph of an instance of a constraint satisfaction problem with n variables and m constraints is the bipartite graph between [m] and [n] describing which variable appears in…
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…
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…