JAIST Repository >
b. 情報科学研究科・情報科学系 >
b10. 学術雑誌論文等 >
b10-1. 雑誌掲載論文 >

このアイテムの引用には次の識別子を使用してください: http://hdl.handle.net/10119/7877

タイトル: Efficient Algorithms for Airline Problem
著者: Nakano, Shin-ichi
Uehara, Ryuhei
Uno, Takeaki
キーワード: Airline problem
approximation algorithm
efficient algorithm
NP-completeness
発行日: 2007
出版者: Springer
誌名: Lecture Notes in Computer Science
巻: 4484
開始ページ: 428
終了ページ: 439
DOI: 10.1007/978-3-540-73001-9_38
抄録: The airlines in the real world form small-world network. This implies that they are constructed with an ad hoc strategy. The small-world network is not so bad from the viewpoints of customers and managers. The customers can fly to any destination through a few airline hubs, and the number of airlines is not so many comparing to the number of airports. However, clearly, it is not the best solution in either viewpoint since there is a trade off. In this paper, one of the extreme cases, which is the standpoint of the manager, is considered; we assume that customers are silent and they never complain even if they are required to transit many times. This assumption is appropriate for some transportation service and packet communication. Under this assumption, the airline problem is to construct the least cost connected network for given distribution of the populations of cities with no a priori connection. First, we show an efficient algorithm that produces a good network which is minimized the number of vacant seats. The resultant network contains at most n connections (or edges), where n is the number of cities. Next we aim to minimize not only the number of vacant seats, but also the number of airline connections. The connected network with the least number of edges is a tree which has exactly n−1 connections. However, the problem to construct a tree airline network with the minimum number of vacant seats is NP-complete. We also propose efficient approximation algorithms to construct a tree airline network with the minimum number of vacant seats.
Rights: This is the author-created version of Springer, Shin-ichi Nakano, Ryuhei Uehara and Takeaki Uno, Lecture Notes in Computer Science, 4484, 2007, 428-439. The original publication is available at www.springerlink.com, http://dx.doi.org/10.1007/978-3-540-73001-9_38
URI: http://hdl.handle.net/10119/7877
資料タイプ: author
出現コレクション:b10-1. 雑誌掲載論文 (Journal Articles)

このアイテムのファイル:

ファイル 記述 サイズ形式
C11144.pdf90KbAdobe PDF見る/開く

当システムに保管されているアイテムはすべて著作権により保護されています。

 


お問い合わせ先 : 北陸先端科学技術大学院大学 研究推進課図書館情報係