138 citations · 191 across the 22 of their papers we have counts for
4 papers · 1 filter
Smoothed Complexity of SWAP in Local Graph Partitioning
Xi Chen, Chenghao Guo, Emmanouil-Vasileios Vlatakis-Gkaragkounis +1
We give the first quasipolynomial upper bound for the smoothed complexity of the SWAP algorithm for local Graph Partitioning (also known as Bisection Width…
Smoothed complexity of local Max-Cut and binary Max-CSP
Xi Chen, Chenghao Guo, Emmanouil-Vasileios Vlatakis-Gkaragkounis +2
We show that the smoothed complexity of the FLIP algorithm for local Max-Cut is at most , where is the number of nodes in the graph and is a…
How good is the Chord algorithm?
Constantinos Daskalakis, Ilias Diakonikolas, Mihalis Yannakakis
The Chord algorithm is a popular, simple method for the succinct approximation of curves, which is widely used, under different names, in a variety of areas, such as, multiobjectiv…
Small Approximate Pareto Sets for Bi-objective Shortest Paths and Other Problems
Ilias Diakonikolas, Mihalis Yannakakis
We investigate the problem of computing a minimum set of solutions that approximates within a specified accuracy the Pareto curve of a multiobjective optimization problem. We s…