부산대학교 도서관

Determining the maximum cut of large graphs may require impractically long time, necessitating approximate algorithms and/or specialized computing platforms. A heuristic by Burer, Monteiro and Zhang for max-cut has not only been shown to be advantageous in many respects, but is also applicable to other NP-complete problems. From the perspective of accelerated computing, the heuristic's implementational challenge lies in its gradient-descent dynamics, which could be reduced to several sinusoidal kernel operations applied to each edge of the graph. We had previously established the theoretical underpinnings of a relaxed dynamical heuristic for max-cut similar to the one proposed by Burer et al. but suited for accelerated computing on custom analog CMOS. In this work, we present the first fully custom analog integrated circuit implementing the dynamics of our heuristic on 130-nm CMOS technology. In an era of increasing specificity of computing machines, our algorithm-circuit co-design, originally for max-cut, introduces a versatile approach applicable to a diverse set of practical large-scale NP-complete problems.