23 citations · 146 across the 41 of their papers we have counts for
3 papers · 2 filters
Local Search is Better than Random Assignment for Bounded Occurrence Ordering k-CSPs
Konstantin Makarychev
We prove that the Bounded Occurrence Ordering k-CSP Problem is not approximation resistant. We give a very simple local search algorithm that always performs better than the random…
Approximation Algorithm for Non-Boolean MAX k-CSP
Konstantin Makarychev, Yury Makarychev
In this paper, we present a randomized polynomial-time approximation algorithm for k-CSPd. In k-CSPd, we are given a set of predicates of arity k over an alphabet of size d. Our go…
Approximation Algorithms for Semi-random Graph Partitioning Problems
Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan
In this paper, we propose and study a new semi-random model for graph partitioning problems. We believe that it captures many properties of real--world instances. The model is more…