Quantum and Simulated Annealing-Based Iterative Algorithms for QUBO Relaxations of the Sparsest $k$-Subgraph Problem
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916944804839424 |
|---|---|
| author | Bihani, Omkar Kužel, Roman Povh, Janez Pucher, Dunja |
| author_facet | Bihani, Omkar Kužel, Roman Povh, Janez Pucher, Dunja |
| contents | In this paper, we introduce three QUBO (Quadratic Unconstrained Binary Optimization) relaxations for the sparsest $k$-subgraph (SkS) problem: a quadratic penalty relaxation, a Lagrangian relaxation, and an augmented Lagrangian relaxation. The effectiveness of these approaches strongly depends on the choice of penalty parameters. We establish theoretical results characterizing the parameter values for which the QUBO relaxations are exact. For practical implementation, we propose three iterative algorithms, which have in their kernel the QUBO relaxations, that update the penalty parameters at each iteration while approximately solving the internal QUBO problems with simulated annealing and quantum processing units. Extensive numerical experiments validate our theoretical findings on exact relaxations and demonstrate the efficiency of the proposed iterative algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_08544 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Quantum and Simulated Annealing-Based Iterative Algorithms for QUBO Relaxations of the Sparsest $k$-Subgraph Problem Bihani, Omkar Kužel, Roman Povh, Janez Pucher, Dunja Optimization and Control 90C27, 81P68 G.4 In this paper, we introduce three QUBO (Quadratic Unconstrained Binary Optimization) relaxations for the sparsest $k$-subgraph (SkS) problem: a quadratic penalty relaxation, a Lagrangian relaxation, and an augmented Lagrangian relaxation. The effectiveness of these approaches strongly depends on the choice of penalty parameters. We establish theoretical results characterizing the parameter values for which the QUBO relaxations are exact. For practical implementation, we propose three iterative algorithms, which have in their kernel the QUBO relaxations, that update the penalty parameters at each iteration while approximately solving the internal QUBO problems with simulated annealing and quantum processing units. Extensive numerical experiments validate our theoretical findings on exact relaxations and demonstrate the efficiency of the proposed iterative algorithms. |
| title | Quantum and Simulated Annealing-Based Iterative Algorithms for QUBO Relaxations of the Sparsest $k$-Subgraph Problem |
| topic | Optimization and Control 90C27, 81P68 G.4 |
| url | https://arxiv.org/abs/2509.08544 |