Fibonacci helps to evacuate from a convex region in a grid network

Lan Qin; Yinfeng Xu

doi:10.1007/s10878-016-9998-7

Fibonacci helps to evacuate from a convex region in a grid network

Lan Qin
, Yinfeng Xu

School of Management

Xi'an Jiaotong University

Research output: Contribution to journal › Article › peer-review

2 Scopus citations

Abstract

This study considers an evacuation problem where the evacuees try to escape to the boundary of an affected area, which is convex, and a grid network is embedded in the area. The boundary is unknown to the evacuees and we propose an online evacuation strategy based on the Fibonacci sequence. This strategy is proved to have a competitive ratio of 19.5, which is better than the best previously reported result of 21.

Original language	English
Pages (from-to)	398-413
Number of pages	16
Journal	Journal of Combinatorial Optimization
Volume	34
Issue number	2
DOIs	https://doi.org/10.1007/s10878-016-9998-7
State	Published - 1 Aug 2017

Keywords

Competitive analysis
Evacuation strategy
Fibonacci sequence
Grid network

Access to Document

10.1007/s10878-016-9998-7

Cite this

@article{50316e7e8c354d4e83dbcdd7fe7f6129,

title = "Fibonacci helps to evacuate from a convex region in a grid network",

abstract = "This study considers an evacuation problem where the evacuees try to escape to the boundary of an affected area, which is convex, and a grid network is embedded in the area. The boundary is unknown to the evacuees and we propose an online evacuation strategy based on the Fibonacci sequence. This strategy is proved to have a competitive ratio of 19.5, which is better than the best previously reported result of 21.",

keywords = "Competitive analysis, Evacuation strategy, Fibonacci sequence, Grid network",

author = "Lan Qin and Yinfeng Xu",

note = "Publisher Copyright: {\textcopyright} 2016, Springer Science+Business Media New York.",

year = "2017",

month = aug,

day = "1",

doi = "10.1007/s10878-016-9998-7",

language = "英语",

volume = "34",

pages = "398--413",

journal = "Journal of Combinatorial Optimization",

issn = "1382-6905",

publisher = "Springer Netherlands",

number = "2",

}

TY - JOUR

T1 - Fibonacci helps to evacuate from a convex region in a grid network

AU - Qin, Lan

AU - Xu, Yinfeng

PY - 2017/8/1

Y1 - 2017/8/1

N2 - This study considers an evacuation problem where the evacuees try to escape to the boundary of an affected area, which is convex, and a grid network is embedded in the area. The boundary is unknown to the evacuees and we propose an online evacuation strategy based on the Fibonacci sequence. This strategy is proved to have a competitive ratio of 19.5, which is better than the best previously reported result of 21.

AB - This study considers an evacuation problem where the evacuees try to escape to the boundary of an affected area, which is convex, and a grid network is embedded in the area. The boundary is unknown to the evacuees and we propose an online evacuation strategy based on the Fibonacci sequence. This strategy is proved to have a competitive ratio of 19.5, which is better than the best previously reported result of 21.

KW - Competitive analysis

KW - Evacuation strategy

KW - Fibonacci sequence

KW - Grid network

UR - https://www.scopus.com/pages/publications/84957657677

U2 - 10.1007/s10878-016-9998-7

DO - 10.1007/s10878-016-9998-7

M3 - 文章

AN - SCOPUS:84957657677

SN - 1382-6905

VL - 34

SP - 398

EP - 413

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

IS - 2

ER -

Fibonacci helps to evacuate from a convex region in a grid network

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this