Details
| Originalsprache | Englisch |
|---|---|
| Titel des Sammelwerks | 2017 IEEE Congress on Evolutionary Computation (CEC) |
| Untertitel | Proceedings |
| Herausgeber (Verlag) | Institute of Electrical and Electronics Engineers Inc. |
| Seiten | 1704-1711 |
| Seitenumfang | 8 |
| ISBN (elektronisch) | 9781509046010 |
| Publikationsstatus | Veröffentlicht - 7 Juli 2017 |
| Extern publiziert | Ja |
| Veranstaltung | 2017 IEEE Congress on Evolutionary Computation, CEC 2017 - Donostia-San Sebastian, Spanien Dauer: 5 Juni 2017 → 8 Juni 2017 |
Abstract
For the minimum vertex cover problem, a wide range of solvers has been proposed over the years. Most classical exact approaches are encountering run time issues on massive graphs that are considered nowadays. A straightforward alternative approach is then to use heuristics, which make assumptions about the structure of the studied graphs. These assumptions are typically hard-coded and are hoped to work well for a wide range of networks - which is in conflict with the nature of broad benchmark sets. With this article, we contribute in two ways. First, we identify a component in an existing solver that influences its performance depending on the class of graphs, and we then customize instances of this solver for different classes of graphs. Second, we create the first algorithm portfolio for the minimum vertex cover to further improve the performance of a single integrated approach to the minimum vertex cover problem.
ASJC Scopus Sachgebiete
- Informatik (insg.)
- Artificial intelligence
- Informatik (insg.)
- Computernetzwerke und -kommunikation
- Informatik (insg.)
- Angewandte Informatik
- Informatik (insg.)
- Signalverarbeitung
Zitieren
- Standard
- Harvard
- Apa
- Vancouver
- BibTex
- RIS
2017 IEEE Congress on Evolutionary Computation (CEC): Proceedings. Institute of Electrical and Electronics Engineers Inc., 2017. S. 1704-1711.
Publikation: Beitrag in Buch/Bericht/Sammelwerk/Konferenzband › Aufsatz in Konferenzband › Forschung › Peer-Review
}
TY - GEN
T1 - Improving local search in a minimum vertex cover solver for classes of networks
AU - Wagner, Markus
AU - Friedrich, Tobias
AU - Lindauer, Marius
N1 - Funding information: M. Lindauer was supported by the DFG (German Research Foundation) under Emmy Noether grant HU 1900/2-1. M. Wagner was supported by the Australian Research Council (DE160100850).
PY - 2017/7/7
Y1 - 2017/7/7
N2 - For the minimum vertex cover problem, a wide range of solvers has been proposed over the years. Most classical exact approaches are encountering run time issues on massive graphs that are considered nowadays. A straightforward alternative approach is then to use heuristics, which make assumptions about the structure of the studied graphs. These assumptions are typically hard-coded and are hoped to work well for a wide range of networks - which is in conflict with the nature of broad benchmark sets. With this article, we contribute in two ways. First, we identify a component in an existing solver that influences its performance depending on the class of graphs, and we then customize instances of this solver for different classes of graphs. Second, we create the first algorithm portfolio for the minimum vertex cover to further improve the performance of a single integrated approach to the minimum vertex cover problem.
AB - For the minimum vertex cover problem, a wide range of solvers has been proposed over the years. Most classical exact approaches are encountering run time issues on massive graphs that are considered nowadays. A straightforward alternative approach is then to use heuristics, which make assumptions about the structure of the studied graphs. These assumptions are typically hard-coded and are hoped to work well for a wide range of networks - which is in conflict with the nature of broad benchmark sets. With this article, we contribute in two ways. First, we identify a component in an existing solver that influences its performance depending on the class of graphs, and we then customize instances of this solver for different classes of graphs. Second, we create the first algorithm portfolio for the minimum vertex cover to further improve the performance of a single integrated approach to the minimum vertex cover problem.
UR - http://www.scopus.com/inward/record.url?scp=85028499133&partnerID=8YFLogxK
U2 - 10.1109/cec.2017.7969507
DO - 10.1109/cec.2017.7969507
M3 - Conference contribution
AN - SCOPUS:85028499133
SP - 1704
EP - 1711
BT - 2017 IEEE Congress on Evolutionary Computation (CEC)
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2017 IEEE Congress on Evolutionary Computation, CEC 2017
Y2 - 5 June 2017 through 8 June 2017
ER -