Dynamical system-based computational models for solving combinatorial optimization on hypergraphs Article Swipe
Mohammad Khairul Bashar
,
Antik Mallick
,
Avik W. Ghosh
,
Nikhil Shukla
·
YOU?
·
· 2022
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2207.09618
YOU?
·
· 2022
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2207.09618
The intrinsic energy minimization in dynamical systems offers a valuable tool for minimizing the objective functions of computationally challenging problems in combinatorial optimization. However, most prior works have focused on mapping such dynamics to combinatorial optimization problems whose objective functions have quadratic degree (e.g., MaxCut); such problems can be represented and analyzed using graphs. However, the work on developing such models for problems that need objective functions with degree greater than two, and subsequently, entail the use of hypergraph data structures, is relatively sparse. In this work, we develop dynamical system-inspired computational models for several such problems. Specifically, we define the 'energy function' for hypergraph-based combinatorial problems ranging from Boolean SAT and its variants to integer factorization, and subsequently, define the resulting system dynamics. We also show that the design approach is applicable to optimization problems with quadratic degree, and use it develop a new dynamical system formulation for minimizing the Ising Hamiltonian. Our work not only expands on the scope of problems that can be directly mapped to, and solved using physics-inspired models, but also creates new opportunities to design high-performance accelerators for solving combinatorial optimization.
Related Topics
Concepts
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/2207.09618
- https://arxiv.org/pdf/2207.09618
- OA Status
- green
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4320512456
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4320512456Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2207.09618Digital Object Identifier
- Title
-
Dynamical system-based computational models for solving combinatorial optimization on hypergraphsWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2022Year of publication
- Publication date
-
2022-07-20Full publication date if available
- Authors
-
Mohammad Khairul Bashar, Antik Mallick, Avik W. Ghosh, Nikhil ShuklaList of authors in order
- Landing page
-
https://arxiv.org/abs/2207.09618Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2207.09618Direct 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/2207.09618Direct OA link when available
- Concepts
-
Hypergraph, Combinatorial optimization, Dynamical systems theory, Optimization problem, Mathematical optimization, Quadratic assignment problem, Quadratic equation, Computer science, Mathematics, Theoretical computer science, Discrete mathematics, Physics, Quantum mechanics, GeometryTop 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/W4320512456 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2207.09618 |
| ids.doi | https://doi.org/10.48550/arxiv.2207.09618 |
| ids.openalex | https://openalex.org/W4320512456 |
| fwci | |
| type | preprint |
| title | Dynamical system-based computational models for solving combinatorial optimization on hypergraphs |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T12292 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 0.9936000108718872 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1707 |
| topics[0].subfield.display_name | Computer Vision and Pattern Recognition |
| topics[0].display_name | Graph Theory and Algorithms |
| topics[1].id | https://openalex.org/T10799 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.9908000230789185 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1707 |
| topics[1].subfield.display_name | Computer Vision and Pattern Recognition |
| topics[1].display_name | Data Visualization and Analytics |
| topics[2].id | https://openalex.org/T10064 |
| topics[2].field.id | https://openalex.org/fields/31 |
| topics[2].field.display_name | Physics and Astronomy |
| topics[2].score | 0.9767000079154968 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/3109 |
| topics[2].subfield.display_name | Statistical and Nonlinear Physics |
| topics[2].display_name | Complex Network Analysis Techniques |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C2781221856 |
| concepts[0].level | 2 |
| concepts[0].score | 0.7522001266479492 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q840247 |
| concepts[0].display_name | Hypergraph |
| concepts[1].id | https://openalex.org/C52692508 |
| concepts[1].level | 2 |
| concepts[1].score | 0.6790511012077332 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q1333872 |
| concepts[1].display_name | Combinatorial optimization |
| concepts[2].id | https://openalex.org/C79379906 |
| concepts[2].level | 2 |
| concepts[2].score | 0.5972617864608765 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q3174497 |
| concepts[2].display_name | Dynamical systems theory |
| concepts[3].id | https://openalex.org/C137836250 |
| concepts[3].level | 2 |
| concepts[3].score | 0.5746455788612366 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q984063 |
| concepts[3].display_name | Optimization problem |
| concepts[4].id | https://openalex.org/C126255220 |
| concepts[4].level | 1 |
| concepts[4].score | 0.5338066220283508 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q141495 |
| concepts[4].display_name | Mathematical optimization |
| concepts[5].id | https://openalex.org/C98036226 |
| concepts[5].level | 3 |
| concepts[5].score | 0.5149322152137756 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q7268356 |
| concepts[5].display_name | Quadratic assignment problem |
| concepts[6].id | https://openalex.org/C129844170 |
| concepts[6].level | 2 |
| concepts[6].score | 0.44846591353416443 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q41299 |
| concepts[6].display_name | Quadratic equation |
| concepts[7].id | https://openalex.org/C41008148 |
| concepts[7].level | 0 |
| concepts[7].score | 0.44089072942733765 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[7].display_name | Computer science |
| concepts[8].id | https://openalex.org/C33923547 |
| concepts[8].level | 0 |
| concepts[8].score | 0.41651827096939087 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[8].display_name | Mathematics |
| concepts[9].id | https://openalex.org/C80444323 |
| concepts[9].level | 1 |
| concepts[9].score | 0.36630746722221375 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q2878974 |
| concepts[9].display_name | Theoretical computer science |
| concepts[10].id | https://openalex.org/C118615104 |
| concepts[10].level | 1 |
| concepts[10].score | 0.13428455591201782 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q121416 |
| concepts[10].display_name | Discrete mathematics |
| concepts[11].id | https://openalex.org/C121332964 |
| concepts[11].level | 0 |
| concepts[11].score | 0.0 |
| 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 |
| concepts[13].id | https://openalex.org/C2524010 |
| concepts[13].level | 1 |
| concepts[13].score | 0.0 |
| concepts[13].wikidata | https://www.wikidata.org/wiki/Q8087 |
| concepts[13].display_name | Geometry |
| keywords[0].id | https://openalex.org/keywords/hypergraph |
| keywords[0].score | 0.7522001266479492 |
| keywords[0].display_name | Hypergraph |
| keywords[1].id | https://openalex.org/keywords/combinatorial-optimization |
| keywords[1].score | 0.6790511012077332 |
| keywords[1].display_name | Combinatorial optimization |
| keywords[2].id | https://openalex.org/keywords/dynamical-systems-theory |
| keywords[2].score | 0.5972617864608765 |
| keywords[2].display_name | Dynamical systems theory |
| keywords[3].id | https://openalex.org/keywords/optimization-problem |
| keywords[3].score | 0.5746455788612366 |
| keywords[3].display_name | Optimization problem |
| keywords[4].id | https://openalex.org/keywords/mathematical-optimization |
| keywords[4].score | 0.5338066220283508 |
| keywords[4].display_name | Mathematical optimization |
| keywords[5].id | https://openalex.org/keywords/quadratic-assignment-problem |
| keywords[5].score | 0.5149322152137756 |
| keywords[5].display_name | Quadratic assignment problem |
| keywords[6].id | https://openalex.org/keywords/quadratic-equation |
| keywords[6].score | 0.44846591353416443 |
| keywords[6].display_name | Quadratic equation |
| keywords[7].id | https://openalex.org/keywords/computer-science |
| keywords[7].score | 0.44089072942733765 |
| keywords[7].display_name | Computer science |
| keywords[8].id | https://openalex.org/keywords/mathematics |
| keywords[8].score | 0.41651827096939087 |
| keywords[8].display_name | Mathematics |
| keywords[9].id | https://openalex.org/keywords/theoretical-computer-science |
| keywords[9].score | 0.36630746722221375 |
| keywords[9].display_name | Theoretical computer science |
| keywords[10].id | https://openalex.org/keywords/discrete-mathematics |
| keywords[10].score | 0.13428455591201782 |
| keywords[10].display_name | Discrete mathematics |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:2207.09618 |
| 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/2207.09618 |
| 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/2207.09618 |
| locations[1].id | doi:10.48550/arxiv.2207.09618 |
| 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.2207.09618 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5038234804 |
| authorships[0].author.orcid | https://orcid.org/0000-0002-3668-0576 |
| authorships[0].author.display_name | Mohammad Khairul Bashar |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Bashar, Mohammad Khairul |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5084638037 |
| authorships[1].author.orcid | https://orcid.org/0000-0002-5697-5742 |
| authorships[1].author.display_name | Antik Mallick |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Mallick, Antik |
| authorships[1].is_corresponding | False |
| authorships[2].author.id | https://openalex.org/A5000227699 |
| authorships[2].author.orcid | https://orcid.org/0000-0002-8020-0760 |
| authorships[2].author.display_name | Avik W. Ghosh |
| authorships[2].author_position | middle |
| authorships[2].raw_author_name | Ghosh, Avik W. |
| 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 | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://arxiv.org/pdf/2207.09618 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | Dynamical system-based computational models for solving combinatorial optimization on hypergraphs |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T12292 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 0.9936000108718872 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1707 |
| primary_topic.subfield.display_name | Computer Vision and Pattern Recognition |
| primary_topic.display_name | Graph Theory and Algorithms |
| related_works | https://openalex.org/W146489555, https://openalex.org/W2547723219, https://openalex.org/W2015483401, https://openalex.org/W2023485317, https://openalex.org/W2013603106, https://openalex.org/W2474680198, https://openalex.org/W90296522, https://openalex.org/W1930648503, https://openalex.org/W2597689725, https://openalex.org/W2049828308 |
| cited_by_count | 0 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:arXiv.org:2207.09618 |
| 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/2207.09618 |
| 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/2207.09618 |
| primary_location.id | pmh:oai:arXiv.org:2207.09618 |
| 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/2207.09618 |
| 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/2207.09618 |
| publication_date | 2022-07-20 |
| publication_year | 2022 |
| referenced_works_count | 0 |
| abstract_inverted_index.a | 8, 143 |
| abstract_inverted_index.In | 84 |
| abstract_inverted_index.We | 124 |
| abstract_inverted_index.be | 48, 165 |
| abstract_inverted_index.in | 4, 20 |
| abstract_inverted_index.is | 81, 131 |
| abstract_inverted_index.it | 141 |
| abstract_inverted_index.of | 16, 77, 161 |
| abstract_inverted_index.on | 29, 57, 158 |
| abstract_inverted_index.to | 33, 114, 133, 179 |
| abstract_inverted_index.we | 87, 98 |
| abstract_inverted_index.Our | 153 |
| abstract_inverted_index.SAT | 110 |
| abstract_inverted_index.The | 0 |
| abstract_inverted_index.and | 50, 72, 111, 117, 139, 169 |
| abstract_inverted_index.but | 174 |
| abstract_inverted_index.can | 47, 164 |
| abstract_inverted_index.for | 11, 61, 93, 103, 148, 183 |
| abstract_inverted_index.its | 112 |
| abstract_inverted_index.new | 144, 177 |
| abstract_inverted_index.not | 155 |
| abstract_inverted_index.the | 13, 55, 75, 100, 120, 128, 150, 159 |
| abstract_inverted_index.to, | 168 |
| abstract_inverted_index.use | 76, 140 |
| abstract_inverted_index.also | 125, 175 |
| abstract_inverted_index.data | 79 |
| abstract_inverted_index.from | 108 |
| abstract_inverted_index.have | 27, 40 |
| abstract_inverted_index.most | 24 |
| abstract_inverted_index.need | 64 |
| abstract_inverted_index.only | 156 |
| abstract_inverted_index.show | 126 |
| abstract_inverted_index.such | 31, 45, 59, 95 |
| abstract_inverted_index.than | 70 |
| abstract_inverted_index.that | 63, 127, 163 |
| abstract_inverted_index.this | 85 |
| abstract_inverted_index.tool | 10 |
| abstract_inverted_index.two, | 71 |
| abstract_inverted_index.with | 67, 136 |
| abstract_inverted_index.work | 56, 154 |
| abstract_inverted_index.Ising | 151 |
| abstract_inverted_index.prior | 25 |
| abstract_inverted_index.scope | 160 |
| abstract_inverted_index.using | 52, 171 |
| abstract_inverted_index.whose | 37 |
| abstract_inverted_index.work, | 86 |
| abstract_inverted_index.works | 26 |
| abstract_inverted_index.(e.g., | 43 |
| abstract_inverted_index.define | 99, 119 |
| abstract_inverted_index.degree | 42, 68 |
| abstract_inverted_index.design | 129, 180 |
| abstract_inverted_index.energy | 2 |
| abstract_inverted_index.entail | 74 |
| abstract_inverted_index.mapped | 167 |
| abstract_inverted_index.models | 60, 92 |
| abstract_inverted_index.offers | 7 |
| abstract_inverted_index.solved | 170 |
| abstract_inverted_index.system | 122, 146 |
| abstract_inverted_index.'energy | 101 |
| abstract_inverted_index.Boolean | 109 |
| abstract_inverted_index.creates | 176 |
| abstract_inverted_index.degree, | 138 |
| abstract_inverted_index.develop | 88, 142 |
| abstract_inverted_index.expands | 157 |
| abstract_inverted_index.focused | 28 |
| abstract_inverted_index.graphs. | 53 |
| abstract_inverted_index.greater | 69 |
| abstract_inverted_index.integer | 115 |
| abstract_inverted_index.mapping | 30 |
| abstract_inverted_index.models, | 173 |
| abstract_inverted_index.ranging | 107 |
| abstract_inverted_index.several | 94 |
| abstract_inverted_index.solving | 184 |
| abstract_inverted_index.sparse. | 83 |
| abstract_inverted_index.systems | 6 |
| abstract_inverted_index.However, | 23, 54 |
| abstract_inverted_index.MaxCut); | 44 |
| abstract_inverted_index.analyzed | 51 |
| abstract_inverted_index.approach | 130 |
| abstract_inverted_index.directly | 166 |
| abstract_inverted_index.dynamics | 32 |
| abstract_inverted_index.problems | 19, 36, 46, 62, 106, 135, 162 |
| abstract_inverted_index.valuable | 9 |
| abstract_inverted_index.variants | 113 |
| abstract_inverted_index.dynamical | 5, 89, 145 |
| abstract_inverted_index.dynamics. | 123 |
| abstract_inverted_index.function' | 102 |
| abstract_inverted_index.functions | 15, 39, 66 |
| abstract_inverted_index.intrinsic | 1 |
| abstract_inverted_index.objective | 14, 38, 65 |
| abstract_inverted_index.problems. | 96 |
| abstract_inverted_index.quadratic | 41, 137 |
| abstract_inverted_index.resulting | 121 |
| abstract_inverted_index.applicable | 132 |
| abstract_inverted_index.developing | 58 |
| abstract_inverted_index.hypergraph | 78 |
| abstract_inverted_index.minimizing | 12, 149 |
| abstract_inverted_index.relatively | 82 |
| abstract_inverted_index.challenging | 18 |
| abstract_inverted_index.formulation | 147 |
| abstract_inverted_index.represented | 49 |
| abstract_inverted_index.structures, | 80 |
| abstract_inverted_index.Hamiltonian. | 152 |
| abstract_inverted_index.accelerators | 182 |
| abstract_inverted_index.minimization | 3 |
| abstract_inverted_index.optimization | 35, 134 |
| abstract_inverted_index.Specifically, | 97 |
| abstract_inverted_index.combinatorial | 21, 34, 105, 185 |
| abstract_inverted_index.computational | 91 |
| abstract_inverted_index.opportunities | 178 |
| abstract_inverted_index.optimization. | 22, 186 |
| abstract_inverted_index.subsequently, | 73, 118 |
| abstract_inverted_index.factorization, | 116 |
| abstract_inverted_index.computationally | 17 |
| abstract_inverted_index.system-inspired | 90 |
| abstract_inverted_index.high-performance | 181 |
| abstract_inverted_index.hypergraph-based | 104 |
| abstract_inverted_index.physics-inspired | 172 |
| 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.8799999952316284 |
| sustainable_development_goals[0].display_name | Affordable and clean energy |
| citation_normalized_percentile |