Computational Models based on Synchronized Oscillators for Solving Combinatorial Optimization Problems Article Swipe
Antik Mallick
,
Mohammad Khairul Bashar
,
Zongli Lin
,
Nikhil Shukla
·
YOU?
·
· 2022
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2206.05907
YOU?
·
· 2022
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2206.05907
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.
Related Topics
Concepts
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/2206.05907
- https://arxiv.org/pdf/2206.05907
- OA Status
- green
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4320206524
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4320206524Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2206.05907Digital Object Identifier
- Title
-
Computational Models based on Synchronized Oscillators for Solving Combinatorial Optimization ProblemsWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2022Year of publication
- Publication date
-
2022-06-13Full publication date if available
- Authors
-
Antik Mallick, Mohammad Khairul Bashar, Zongli Lin, Nikhil ShuklaList of authors in order
- Landing page
-
https://arxiv.org/abs/2206.05907Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2206.05907Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://arxiv.org/pdf/2206.05907Direct OA link when available
- Concepts
-
Combinatorial optimization, Optimization problem, Mathematical optimization, Travelling salesman problem, Computer science, Dynamical systems theory, Harmonic oscillator, Minification, Energy minimization, Theoretical computer science, Mathematics, Physics, Quantum mechanicsTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4320206524 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2206.05907 |
| ids.doi | https://doi.org/10.48550/arxiv.2206.05907 |
| ids.openalex | https://openalex.org/W4320206524 |
| fwci | |
| type | preprint |
| title | Computational Models based on Synchronized Oscillators for Solving Combinatorial Optimization Problems |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T12029 |
| topics[0].field.id | https://openalex.org/fields/13 |
| topics[0].field.display_name | Biochemistry, Genetics and Molecular Biology |
| topics[0].score | 0.9878000020980835 |
| topics[0].domain.id | https://openalex.org/domains/1 |
| topics[0].domain.display_name | Life Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1312 |
| topics[0].subfield.display_name | Molecular Biology |
| topics[0].display_name | DNA and Biological Computing |
| topics[1].id | https://openalex.org/T10913 |
| topics[1].field.id | https://openalex.org/fields/22 |
| topics[1].field.display_name | Engineering |
| topics[1].score | 0.9869999885559082 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/2208 |
| topics[1].subfield.display_name | Electrical and Electronic Engineering |
| topics[1].display_name | Molecular Junctions and Nanostructures |
| topics[2].id | https://openalex.org/T10363 |
| topics[2].field.id | https://openalex.org/fields/22 |
| topics[2].field.display_name | Engineering |
| topics[2].score | 0.9678000211715698 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/2208 |
| topics[2].subfield.display_name | Electrical and Electronic Engineering |
| topics[2].display_name | Low-power high-performance VLSI design |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C52692508 |
| concepts[0].level | 2 |
| concepts[0].score | 0.6851836442947388 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q1333872 |
| concepts[0].display_name | Combinatorial optimization |
| concepts[1].id | https://openalex.org/C137836250 |
| concepts[1].level | 2 |
| concepts[1].score | 0.5940752625465393 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q984063 |
| concepts[1].display_name | Optimization problem |
| concepts[2].id | https://openalex.org/C126255220 |
| concepts[2].level | 1 |
| concepts[2].score | 0.5916100740432739 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q141495 |
| concepts[2].display_name | Mathematical optimization |
| concepts[3].id | https://openalex.org/C175859090 |
| concepts[3].level | 2 |
| concepts[3].score | 0.5712969303131104 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q322212 |
| concepts[3].display_name | Travelling salesman problem |
| concepts[4].id | https://openalex.org/C41008148 |
| concepts[4].level | 0 |
| concepts[4].score | 0.5687369704246521 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[4].display_name | Computer science |
| concepts[5].id | https://openalex.org/C79379906 |
| concepts[5].level | 2 |
| concepts[5].score | 0.5530295968055725 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q3174497 |
| concepts[5].display_name | Dynamical systems theory |
| concepts[6].id | https://openalex.org/C40934718 |
| concepts[6].level | 2 |
| concepts[6].score | 0.5074524283409119 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q190070 |
| concepts[6].display_name | Harmonic oscillator |
| concepts[7].id | https://openalex.org/C147764199 |
| concepts[7].level | 2 |
| concepts[7].score | 0.4668691158294678 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q6865248 |
| concepts[7].display_name | Minification |
| concepts[8].id | https://openalex.org/C14961307 |
| concepts[8].level | 2 |
| concepts[8].score | 0.45378515124320984 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q5377176 |
| concepts[8].display_name | Energy minimization |
| concepts[9].id | https://openalex.org/C80444323 |
| concepts[9].level | 1 |
| concepts[9].score | 0.3298233151435852 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q2878974 |
| concepts[9].display_name | Theoretical computer science |
| concepts[10].id | https://openalex.org/C33923547 |
| concepts[10].level | 0 |
| concepts[10].score | 0.2986871004104614 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[10].display_name | Mathematics |
| concepts[11].id | https://openalex.org/C121332964 |
| concepts[11].level | 0 |
| concepts[11].score | 0.1045723557472229 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q413 |
| concepts[11].display_name | Physics |
| concepts[12].id | https://openalex.org/C62520636 |
| concepts[12].level | 1 |
| concepts[12].score | 0.0 |
| concepts[12].wikidata | https://www.wikidata.org/wiki/Q944 |
| concepts[12].display_name | Quantum mechanics |
| keywords[0].id | https://openalex.org/keywords/combinatorial-optimization |
| keywords[0].score | 0.6851836442947388 |
| keywords[0].display_name | Combinatorial optimization |
| keywords[1].id | https://openalex.org/keywords/optimization-problem |
| keywords[1].score | 0.5940752625465393 |
| keywords[1].display_name | Optimization problem |
| keywords[2].id | https://openalex.org/keywords/mathematical-optimization |
| keywords[2].score | 0.5916100740432739 |
| keywords[2].display_name | Mathematical optimization |
| keywords[3].id | https://openalex.org/keywords/travelling-salesman-problem |
| keywords[3].score | 0.5712969303131104 |
| keywords[3].display_name | Travelling salesman problem |
| keywords[4].id | https://openalex.org/keywords/computer-science |
| keywords[4].score | 0.5687369704246521 |
| keywords[4].display_name | Computer science |
| keywords[5].id | https://openalex.org/keywords/dynamical-systems-theory |
| keywords[5].score | 0.5530295968055725 |
| keywords[5].display_name | Dynamical systems theory |
| keywords[6].id | https://openalex.org/keywords/harmonic-oscillator |
| keywords[6].score | 0.5074524283409119 |
| keywords[6].display_name | Harmonic oscillator |
| keywords[7].id | https://openalex.org/keywords/minification |
| keywords[7].score | 0.4668691158294678 |
| keywords[7].display_name | Minification |
| keywords[8].id | https://openalex.org/keywords/energy-minimization |
| keywords[8].score | 0.45378515124320984 |
| keywords[8].display_name | Energy minimization |
| keywords[9].id | https://openalex.org/keywords/theoretical-computer-science |
| keywords[9].score | 0.3298233151435852 |
| keywords[9].display_name | Theoretical computer science |
| keywords[10].id | https://openalex.org/keywords/mathematics |
| keywords[10].score | 0.2986871004104614 |
| keywords[10].display_name | Mathematics |
| keywords[11].id | https://openalex.org/keywords/physics |
| keywords[11].score | 0.1045723557472229 |
| keywords[11].display_name | Physics |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:2206.05907 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306400194 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | True |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | arXiv (Cornell University) |
| locations[0].source.host_organization | https://openalex.org/I205783295 |
| locations[0].source.host_organization_name | Cornell University |
| locations[0].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[0].license | |
| locations[0].pdf_url | https://arxiv.org/pdf/2206.05907 |
| locations[0].version | submittedVersion |
| locations[0].raw_type | |
| locations[0].license_id | |
| locations[0].is_accepted | False |
| locations[0].is_published | False |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | http://arxiv.org/abs/2206.05907 |
| locations[1].id | doi:10.48550/arxiv.2206.05907 |
| locations[1].is_oa | True |
| locations[1].source.id | https://openalex.org/S4306400194 |
| locations[1].source.issn | |
| locations[1].source.type | repository |
| locations[1].source.is_oa | True |
| locations[1].source.issn_l | |
| locations[1].source.is_core | False |
| locations[1].source.is_in_doaj | False |
| locations[1].source.display_name | arXiv (Cornell University) |
| locations[1].source.host_organization | https://openalex.org/I205783295 |
| locations[1].source.host_organization_name | Cornell University |
| locations[1].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[1].license | |
| locations[1].pdf_url | |
| locations[1].version | |
| locations[1].raw_type | article |
| locations[1].license_id | |
| locations[1].is_accepted | False |
| locations[1].is_published | |
| locations[1].raw_source_name | |
| locations[1].landing_page_url | https://doi.org/10.48550/arxiv.2206.05907 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5084638037 |
| authorships[0].author.orcid | https://orcid.org/0000-0002-5697-5742 |
| authorships[0].author.display_name | Antik Mallick |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Mallick, Antik |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5038234804 |
| authorships[1].author.orcid | https://orcid.org/0000-0002-3668-0576 |
| authorships[1].author.display_name | Mohammad Khairul Bashar |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Bashar, Mohammad Khairul |
| authorships[1].is_corresponding | False |
| authorships[2].author.id | https://openalex.org/A5072774939 |
| authorships[2].author.orcid | https://orcid.org/0000-0003-1589-1443 |
| authorships[2].author.display_name | Zongli Lin |
| authorships[2].author_position | middle |
| authorships[2].raw_author_name | Lin, Zongli |
| authorships[2].is_corresponding | False |
| authorships[3].author.id | https://openalex.org/A5028883225 |
| authorships[3].author.orcid | https://orcid.org/0000-0002-8899-5190 |
| authorships[3].author.display_name | Nikhil Shukla |
| authorships[3].author_position | last |
| authorships[3].raw_author_name | Shukla, Nikhil |
| authorships[3].is_corresponding | False |
| has_content.pdf | True |
| has_content.grobid_xml | True |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://arxiv.org/pdf/2206.05907 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2023-02-13T00:00:00 |
| display_name | Computational Models based on Synchronized Oscillators for Solving Combinatorial Optimization Problems |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T12029 |
| primary_topic.field.id | https://openalex.org/fields/13 |
| primary_topic.field.display_name | Biochemistry, Genetics and Molecular Biology |
| primary_topic.score | 0.9878000020980835 |
| primary_topic.domain.id | https://openalex.org/domains/1 |
| primary_topic.domain.display_name | Life Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1312 |
| primary_topic.subfield.display_name | Molecular Biology |
| primary_topic.display_name | DNA and Biological Computing |
| related_works | https://openalex.org/W2572756133, https://openalex.org/W1563568831, https://openalex.org/W2135149549, https://openalex.org/W4294358747, https://openalex.org/W1604040598, https://openalex.org/W2946024655, https://openalex.org/W2861856156, https://openalex.org/W2146364482, https://openalex.org/W2758988501, https://openalex.org/W4236147943 |
| cited_by_count | 0 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:arXiv.org:2206.05907 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306400194 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | True |
| best_oa_location.source.issn_l | |
| best_oa_location.source.is_core | False |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | arXiv (Cornell University) |
| best_oa_location.source.host_organization | https://openalex.org/I205783295 |
| best_oa_location.source.host_organization_name | Cornell University |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| best_oa_location.license | |
| best_oa_location.pdf_url | https://arxiv.org/pdf/2206.05907 |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | |
| best_oa_location.license_id | |
| best_oa_location.is_accepted | False |
| best_oa_location.is_published | False |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | http://arxiv.org/abs/2206.05907 |
| primary_location.id | pmh:oai:arXiv.org:2206.05907 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306400194 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | True |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | arXiv (Cornell University) |
| primary_location.source.host_organization | https://openalex.org/I205783295 |
| primary_location.source.host_organization_name | Cornell University |
| primary_location.source.host_organization_lineage | https://openalex.org/I205783295 |
| primary_location.license | |
| primary_location.pdf_url | https://arxiv.org/pdf/2206.05907 |
| primary_location.version | submittedVersion |
| primary_location.raw_type | |
| primary_location.license_id | |
| primary_location.is_accepted | False |
| primary_location.is_published | False |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | http://arxiv.org/abs/2206.05907 |
| publication_date | 2022-06-13 |
| publication_year | 2022 |
| referenced_works_count | 0 |
| abstract_inverted_index.a | 9, 20, 25, 72, 92, 148 |
| abstract_inverted_index.We | 116 |
| abstract_inverted_index.an | 16 |
| abstract_inverted_index.be | 54, 123 |
| abstract_inverted_index.by | 132 |
| abstract_inverted_index.in | 8, 79 |
| abstract_inverted_index.of | 6, 15, 45, 61, 75, 95, 106, 155, 163 |
| abstract_inverted_index.on | 71, 87 |
| abstract_inverted_index.to | 28, 57, 111, 125, 142 |
| abstract_inverted_index.we | 82 |
| abstract_inverted_index.Cut | 64, 109 |
| abstract_inverted_index.For | 39 |
| abstract_inverted_index.Our | 145 |
| abstract_inverted_index.The | 0 |
| abstract_inverted_index.and | 12, 34, 138, 159 |
| abstract_inverted_index.can | 53, 122 |
| abstract_inverted_index.for | 36, 91, 167 |
| abstract_inverted_index.has | 69 |
| abstract_inverted_index.set | 74 |
| abstract_inverted_index.the | 3, 13, 41, 58, 62, 101, 107, 112, 135, 139, 143, 153, 161 |
| abstract_inverted_index.(the | 103 |
| abstract_inverted_index.from | 100 |
| abstract_inverted_index.show | 117 |
| abstract_inverted_index.step | 149 |
| abstract_inverted_index.such | 37, 76 |
| abstract_inverted_index.that | 118 |
| abstract_inverted_index.this | 80 |
| abstract_inverted_index.work | 68, 146 |
| abstract_inverted_index.based | 86 |
| abstract_inverted_index.broad | 93 |
| abstract_inverted_index.marks | 147 |
| abstract_inverted_index.prior | 67 |
| abstract_inverted_index.scope | 162 |
| abstract_inverted_index.solve | 126 |
| abstract_inverted_index.state | 43 |
| abstract_inverted_index.these | 127 |
| abstract_inverted_index.under | 49 |
| abstract_inverted_index.work, | 81 |
| abstract_inverted_index.analog | 157 |
| abstract_inverted_index.energy | 7, 44 |
| abstract_inverted_index.ground | 42 |
| abstract_inverted_index.mapped | 56 |
| abstract_inverted_index.models | 33, 85 |
| abstract_inverted_index.offers | 24 |
| abstract_inverted_index.second | 50 |
| abstract_inverted_index.system | 11, 165 |
| abstract_inverted_index.Maximum | 63, 108 |
| abstract_inverted_index.between | 2 |
| abstract_inverted_index.coupled | 46 |
| abstract_inverted_index.focused | 70 |
| abstract_inverted_index.forward | 150 |
| abstract_inverted_index.general | 104 |
| abstract_inverted_index.limited | 73 |
| abstract_inverted_index.natural | 4 |
| abstract_inverted_index.optimal | 59 |
| abstract_inverted_index.problem | 23 |
| abstract_inverted_index.ranging | 99 |
| abstract_inverted_index.solvers | 35, 166 |
| abstract_inverted_index.towards | 151 |
| abstract_inverted_index.version | 105 |
| abstract_inverted_index.However, | 66 |
| abstract_inverted_index.Problem. | 115 |
| abstract_inverted_index.Salesman | 114 |
| abstract_inverted_index.approach | 27 |
| abstract_inverted_index.coupling | 136 |
| abstract_inverted_index.directly | 55 |
| abstract_inverted_index.dynamics | 90, 121 |
| abstract_inverted_index.external | 140 |
| abstract_inverted_index.function | 18, 137 |
| abstract_inverted_index.furthers | 160 |
| abstract_inverted_index.harmonic | 51 |
| abstract_inverted_index.problem) | 110 |
| abstract_inverted_index.problem. | 65 |
| abstract_inverted_index.problems | 98, 131 |
| abstract_inverted_index.solution | 60 |
| abstract_inverted_index.spectrum | 94 |
| abstract_inverted_index.Max-K-Cut | 102 |
| abstract_inverted_index.Traveling | 113 |
| abstract_inverted_index.computing | 84 |
| abstract_inverted_index.designing | 29, 134 |
| abstract_inverted_index.different | 128 |
| abstract_inverted_index.dynamical | 10, 30, 164 |
| abstract_inverted_index.expanding | 152 |
| abstract_inverted_index.formulate | 83 |
| abstract_inverted_index.injection | 141 |
| abstract_inverted_index.instance, | 40 |
| abstract_inverted_index.objective | 17 |
| abstract_inverted_index.problems. | 38, 77, 170 |
| abstract_inverted_index.promising | 26 |
| abstract_inverted_index.Therefore, | 78 |
| abstract_inverted_index.electronic | 47 |
| abstract_inverted_index.engineered | 124 |
| abstract_inverted_index.injection, | 52 |
| abstract_inverted_index.oscillator | 89, 120 |
| abstract_inverted_index.equivalence | 1 |
| abstract_inverted_index.accelerators | 158 |
| abstract_inverted_index.minimization | 5, 14 |
| abstract_inverted_index.optimization | 22, 97, 130, 169 |
| abstract_inverted_index.oscillators, | 48 |
| abstract_inverted_index.oscillators. | 144 |
| abstract_inverted_index.synchronized | 88, 119 |
| abstract_inverted_index.appropriately | 133 |
| abstract_inverted_index.combinatorial | 21, 96, 129, 168 |
| abstract_inverted_index.computational | 32 |
| abstract_inverted_index.characterizing | 19 |
| abstract_inverted_index.functionalities | 154 |
| abstract_inverted_index.system-inspired | 31 |
| abstract_inverted_index.oscillator-based | 156 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 4 |
| sustainable_development_goals[0].id | https://metadata.un.org/sdg/7 |
| sustainable_development_goals[0].score | 0.8600000143051147 |
| sustainable_development_goals[0].display_name | Affordable and clean energy |
| citation_normalized_percentile |