2022/06/13 by Antik Mallick, Mallick, Antik, Mohammad Khairul Bashar +5 · 3 citations
Biochemistry, Genetics and Molecular Biology · Engineering · #Computational Complexity (cs.CC) #DNA and Biological Computing #FOS: Computer and information sciences #FOS: Mathematics #Low-power high-performance VLSI design #Molecular Junctions and Nanostructures #Optimization and Control (math.OC)
paper · pdf · doi:10.48550/arxiv.2206.05907
openalex publication_date 2022/06/13 · openalex created_date 2023/02/13 · openalex updated_date 2026/07/28
The equivalence between the natural minimization of energy in a dynamical system and the minimization of an objective function characterizing a combinatorial optimization problem offers a promising approach to designing dynamical system-inspired computational models and solvers for such problems. For instance, the ground state energy of coupled electronic oscillators, under second harmonic injection, can be directly mapped to the optimal solution of the Maximum Cut problem. However, prior work has focused on a limited set of such problems. Therefore, in this work, we formulate computing models based on synchronized oscillator dynamics for a broad spectrum of combinatorial optimization problems ranging from the Max-K-Cut (the general version of the Maximum Cut problem) to the Traveling Salesman Problem. We show that synchronized oscillator dynamics can be engineered to solve these different combinatorial optimization problems by appropriately designing the coupling function and the external injection to the oscillators. Our work marks a step forward towards expanding the functionalities of oscillator-based analog accelerators and furthers the scope of dynamical system solvers for combinatorial optimization problems.