IEICE TRANSACTIONS on Information
Pseudo Polynomial Time Algorithms for Optimal Longcut Route Selection
Summary :
Users of wireless mobile devices need Internet access not only when they stay at home or office, but also when they travel. It may be desirable for such users to select a "longcut route" from their current location to his/her destination that has longer travel time than the shortest route, but provides a better mobile wireless environment. In this paper, we formulate the above situation as the optimization problem of “optimal longcut route selection”, which requires us to find the best route concerning the wireless environment subject to a travel time constraint. For this new problem, we show NP-hardness, propose two pseudo-polynomial time algorithms, and experimental evaluation of the algorithms.
- Publication
- IEICE TRANSACTIONS on Information Vol.E98-D No.3 pp.607-616
- Publication Date
- 2015/03/01
- Publicized
- 2014/11/25
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2014EDP7278
- Type of Manuscript
- PAPER
- Category
- Fundamentals of Information Systems
Authors
Yuichi SUDO
NTT Corporation,Osaka University
Toshimitsu MASUZAWA
Osaka University
Gen MOTOYOSHI
NEC Corporation
Tutomu MURASE
NEC Corporation
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Yuichi SUDO, Toshimitsu MASUZAWA, Gen MOTOYOSHI, Tutomu MURASE, "Pseudo Polynomial Time Algorithms for Optimal Longcut Route Selection" in IEICE TRANSACTIONS on Information,
vol. E98-D, no. 3, pp. 607-616, March 2015, doi: 10.1587/transinf.2014EDP7278.
Abstract: Users of wireless mobile devices need Internet access not only when they stay at home or office, but also when they travel. It may be desirable for such users to select a "longcut route" from their current location to his/her destination that has longer travel time than the shortest route, but provides a better mobile wireless environment. In this paper, we formulate the above situation as the optimization problem of “optimal longcut route selection”, which requires us to find the best route concerning the wireless environment subject to a travel time constraint. For this new problem, we show NP-hardness, propose two pseudo-polynomial time algorithms, and experimental evaluation of the algorithms.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2014EDP7278/_p
Copy
@ARTICLE{e98-d_3_607,
author={Yuichi SUDO, Toshimitsu MASUZAWA, Gen MOTOYOSHI, Tutomu MURASE, },
journal={IEICE TRANSACTIONS on Information},
title={Pseudo Polynomial Time Algorithms for Optimal Longcut Route Selection},
year={2015},
volume={E98-D},
number={3},
pages={607-616},
abstract={Users of wireless mobile devices need Internet access not only when they stay at home or office, but also when they travel. It may be desirable for such users to select a "longcut route" from their current location to his/her destination that has longer travel time than the shortest route, but provides a better mobile wireless environment. In this paper, we formulate the above situation as the optimization problem of “optimal longcut route selection”, which requires us to find the best route concerning the wireless environment subject to a travel time constraint. For this new problem, we show NP-hardness, propose two pseudo-polynomial time algorithms, and experimental evaluation of the algorithms.},
keywords={},
doi={10.1587/transinf.2014EDP7278},
ISSN={1745-1361},
month={March},}
Copy
TY - JOUR
TI - Pseudo Polynomial Time Algorithms for Optimal Longcut Route Selection
T2 - IEICE TRANSACTIONS on Information
SP - 607
EP - 616
AU - Yuichi SUDO
AU - Toshimitsu MASUZAWA
AU - Gen MOTOYOSHI
AU - Tutomu MURASE
PY - 2015
DO - 10.1587/transinf.2014EDP7278
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E98-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2015
AB - Users of wireless mobile devices need Internet access not only when they stay at home or office, but also when they travel. It may be desirable for such users to select a "longcut route" from their current location to his/her destination that has longer travel time than the shortest route, but provides a better mobile wireless environment. In this paper, we formulate the above situation as the optimization problem of “optimal longcut route selection”, which requires us to find the best route concerning the wireless environment subject to a travel time constraint. For this new problem, we show NP-hardness, propose two pseudo-polynomial time algorithms, and experimental evaluation of the algorithms.
ER -
English
