Studying the effects of instance structure in algorithm performance
the amount of resources consumed in the worst case. However, it has become evident that the instance size by itself is an insufficient measure and that the worst-case scenario is often unin-formative in practice. As a complementary analysis, we propose the examination of structural properties presen...
| Autores principales: | , |
|---|---|
| Formato: | Artículo |
| Lenguaje: | Spanish / Castilian |
| Publicado: |
2006
|
| Materias: | |
| Acceso en línea: | http://eprints.uanl.mx/25393/1/25393.pdf |
| _version_ | 1824420197473189888 |
|---|---|
| author | Turrubiates López, Tania Schaeffer, Satu Elisa |
| author_facet | Turrubiates López, Tania Schaeffer, Satu Elisa |
| author_sort | Turrubiates López, Tania |
| collection | Repositorio Institucional |
| description | the amount of resources consumed in the worst case. However, it has become evident that the instance size by itself is an insufficient measure and that the worst-case scenario is often unin-formative in practice. As a complementary analysis, we propose the examination of structural properties present in the instances and the effects they have on algorithm performance; our goal is to characterize complexity in terms of instance structure. We propose a framework for identifying and characterizing hard instances based on algorithm behaviour as well as a case study applying the framework on the graph coloring problem. |
| format | Article |
| id | eprints-25393 |
| institution | UANL |
| language | Spanish / Castilian |
| publishDate | 2006 |
| record_format | eprints |
| spelling | eprints-253932023-04-28T21:53:38Z http://eprints.uanl.mx/25393/ Studying the effects of instance structure in algorithm performance Turrubiates López, Tania Schaeffer, Satu Elisa QA Matemáticas, Ciencias computacionales the amount of resources consumed in the worst case. However, it has become evident that the instance size by itself is an insufficient measure and that the worst-case scenario is often unin-formative in practice. As a complementary analysis, we propose the examination of structural properties present in the instances and the effects they have on algorithm performance; our goal is to characterize complexity in terms of instance structure. We propose a framework for identifying and characterizing hard instances based on algorithm behaviour as well as a case study applying the framework on the graph coloring problem. 2006 Article NonPeerReviewed text es cc_by_nc_nd http://eprints.uanl.mx/25393/1/25393.pdf http://eprints.uanl.mx/25393/1.haspreviewThumbnailVersion/25393.pdf Turrubiates López, Tania y Schaeffer, Satu Elisa (2006) Studying the effects of instance structure in algorithm performance. Complexity, Cybernetics, and Informing Science and Engineering PORTUGAL. |
| spellingShingle | QA Matemáticas, Ciencias computacionales Turrubiates López, Tania Schaeffer, Satu Elisa Studying the effects of instance structure in algorithm performance |
| thumbnail | https://rediab.uanl.mx/themes/sandal5/images/online.png |
| title | Studying the effects of instance structure in algorithm performance |
| title_full | Studying the effects of instance structure in algorithm performance |
| title_fullStr | Studying the effects of instance structure in algorithm performance |
| title_full_unstemmed | Studying the effects of instance structure in algorithm performance |
| title_short | Studying the effects of instance structure in algorithm performance |
| title_sort | studying the effects of instance structure in algorithm performance |
| topic | QA Matemáticas, Ciencias computacionales |
| url | http://eprints.uanl.mx/25393/1/25393.pdf |
| work_keys_str_mv | AT turrubiateslopeztania studyingtheeffectsofinstancestructureinalgorithmperformance AT schaeffersatuelisa studyingtheeffectsofinstancestructureinalgorithmperformance |