235 citations · 345 across the 30 of their papers we have counts for
Showing 2016Show all
2 papers · 1 filter
cond-mat.dis-nn2016★ 4 cited
Typical Performance of Approximation Algorithms for NP-hard Problems
Satoshi Takabe, Koji Hukushima
Typical performance of approximation algorithms is studied for randomized minimum vertex cover problems. A wide class of random graph ensembles characterized by an arbitrary degree…
cond-mat.dis-nn2016★ 4 cited
Statistical-mechanical Analysis of Linear Programming Relaxation for Combinatorial Optimization Problems
Satoshi Takabe, Koji Hukushima
Typical behavior of the linear programming (LP) problem is studied as a relaxation of the minimum vertex cover, a type of integer programming (IP) problem. A lattice-gas model on t…