Análisis de heurísticos para el problema del cartero rural

1. Benavent López, Enric
2. Campos Aucejo, Vicente
3. Corberán Salvador, Ángel
4. Mota Vidal, Enrique

Esportatu

Esportatu

×

MLA

modern-language-association

APA

apa

Chicago

chicago-fullnote-bibliography

Harvard

harvard-cite-them-right

Vancouver

vancouver-author-date

---

RIS BibTex

Esportatu

×

Dokumentua ezin da beste atari batetik esportatu.

Testu osoa

lock_openTestu osoa externo

DOI: 10.1007/BF02888609 DIALNET GOOGLE SCHOLAR lock_openSarbide irekia editor

Beste argitalpen batzuk: Trabajos de estadística e investigación operativa

Laburpena

In this paper we study the worst case performance of two heuristic algorithms proposed for the Rural Postman Problem on a non directed graph (RPP) and on a directed graph (DRPP). In both cases the worst case ratio is obtained; for the RPP this ratio is 3/2, whereas for the DRPP the ratio is unbounded. In order to obtain more significant bounds, this ratio has also been obtained as a function of certain parameters that can be computed from the particular data of each instance, thus producing a finite bound for the worst case ratio of the heuristic algorithm for the DRPP.

Datuen iturria: Dialnet