On the Complexity of Combinatorial Optimization on Fixed Structures
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912133741019136 |
|---|---|
| author | Megiddo, Nimrod |
| author_facet | Megiddo, Nimrod |
| contents | Combinatorial optimization can be described as the problem of finding a feasible subset that maximizes a objective function. The paper discusses combinatorial optimization problems, where for each dimension the set of feasible subsets is fixed. It is demonstrated that in some cases fixing the structure makes the problem easier, whereas in general the problem remains NP-complete. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_16963 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the Complexity of Combinatorial Optimization on Fixed Structures Megiddo, Nimrod Computational Complexity Combinatorial optimization can be described as the problem of finding a feasible subset that maximizes a objective function. The paper discusses combinatorial optimization problems, where for each dimension the set of feasible subsets is fixed. It is demonstrated that in some cases fixing the structure makes the problem easier, whereas in general the problem remains NP-complete. |
| title | On the Complexity of Combinatorial Optimization on Fixed Structures |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2411.16963 |