du.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • chicago-author-date
  • chicago-note-bibliography
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
GRASP and Statistical Bounds for Heuristic Solutions to Combinatorial Problems
Högskolan Dalarna, Akademin Industri och samhälle, Mikrodataanalys.ORCID-id: 0000-0003-4212-8582
Högskolan Dalarna, Akademin Industri och samhälle, Mikrodataanalys.ORCID-id: 0000-0003-2317-9157
2019 (Engelska)Ingår i: International Journal of Management and Applied Science, ISSN 2394-7926, Vol. 5, nr 8, s. 113-119Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

The quality of a heuristic solution to a NP-hard combinatorial problem is hard to assess. A few studies have advocated and tested statistical bounds as a method for assessment. These studies indicate that statistical bounds are superior to the more widely known and used deterministic bounds. However, the previous studies have been limited to a few heuristics and combinatorial problems and, hence, the general performance of statistical bounds in combinatorial optimization remains an open question. This work complements the existing literature on statistical bounds by testing them on the metaheuristic Greedy Randomized Adaptive Search Procedures (GRASP) and four combinatorial problems. Our findings confirm previous results that statistical bounds are reliable for the p-median problem, while we note that they also seem reliable for the set covering problem. For the quadratic assignment problem, the statistical bounds have previously been found reliable when obtained from the Genetic algorithm whereas in this work they have been found less reliable. Finally, we provide statistical bounds to four 2-path network design problem instances for which the optimum is currently unknown.

Ort, förlag, år, upplaga, sidor
Institute of Research and Journals (IRAJ) , 2019. Vol. 5, nr 8, s. 113-119
Nyckelord [en]
Combinatorial Problems, GRASP, Statistical Bounds, Statistical Optimum Estimation Techniques
Nationell ämneskategori
Annan data- och informationsvetenskap
Forskningsämne
Komplexa system - mikrodataanalys, Allmänt Mikrodataaanalys - metod
Identifikatorer
URN: urn:nbn:se:du-31077OAI: oai:DiVA.org:du-31077DiVA, id: diva2:1368074
Tillgänglig från: 2019-11-05 Skapad: 2019-11-05 Senast uppdaterad: 2019-11-08Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

http://ijmas.iraj.in/paper_detail.php?paper_id=16017&name=GRASP_and_Statistical_Bounds_for_Heuristic_Solutions_to_Combinatorial_Problems

Personposter BETA

Han, MengjieCarling, Kenneth

Sök vidare i DiVA

Av författaren/redaktören
Han, MengjieCarling, Kenneth
Av organisationen
Mikrodataanalys
Annan data- och informationsvetenskap

Sök vidare utanför DiVA

GoogleGoogle Scholar

urn-nbn

Altmetricpoäng

urn-nbn
Totalt: 26 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • chicago-author-date
  • chicago-note-bibliography
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf