A Linear Relaxation for Hub Network Design Problems(Special Section on Discrete Mathematics and Its Applications)
スポンサーリンク
概要
- 論文の詳細を見る
In this paper, we consider a network design problem with hub-and-spoke structure. We propose a relaxation technique for the problem where the location of hub nodes is given and decides the allocation of non-hub nodes to one of the hub nodes. We linearize the non-convex quadratic objective function of the original problem, introducing Hitchcock transportation problems defined for each pair of non-hub nodes. We provide two linear relaxation problems, one based on the Hitchcock transportation problems and the other on the dual Hitchcock transportation problems. We show the tightness of the lower bounds obtained by our formulations by computational experiences.
- 社団法人電子情報通信学会の論文
- 2002-05-01
著者
-
Matsui Tomomi
University of Tokyo
-
Matsui T
Univ. Tokyo Tokyo Jpn
-
Saito Hiro-o
The Authors Are With The Department Of Mathematical Informatics Graduate School Of Information Scien
-
Matsui Tomomi
Faculty Of Science And Engineering Chuo University
-
Matsui Tomomi
Department Of Mathematical Informatics Graduate School Of Information Science And Technology The Uni
-
Matsui Tomomi
Univ. Of Tokyo
-
Matsui Tomomi
The Authors Are With The Department Of Mathematical Informatics Graduate School Of Information Scien
-
MATUURA Shiro
The authors are with the Department of Mathematical Informatics, Graduate School of Information Scie
-
Matuura S
University Of Tokyo
-
Matsui Tomomi
Department Of Mathematical Informatics Graduate School Of Information Science And Technology The Uni
関連論文
- LINEAR TIME APPROXIMATION ALGORITHM FOR MULTICOLORING LATTICE GRAPHS WITH DIAGONALS
- Successful Manipulation in Stable Marriage Model with Complete Preference Lists
- 2-C-14 Cheating Strategies for Gale-Shapley Algorithm with Complete Preference Lists
- A note on Asymmetric Power Index for Voting Games
- A note on mixed level supersaturated designs
- Approximate Counting Scheme for m×n Contingency Tables(Foundations of Computer Science)
- Dependent Randomized Rounding to the Home-Away Assignment Problem in Sports Scheduling(Discrete Mathematics and Its Applications)
- Home-Away Table Feasibility Problem
- Notes on Equitable Round-Robin Tournaments(Special Section on Discrete Mathematics and Its Applications)
- Polynomial time approximate or perfect samplers for discretized Dirichlet distribution
- A Linear Relaxation for Hub Network Design Problems(Special Section on Discrete Mathematics and Its Applications)
- Linear Relaxation for Hub Network Design Problems
- DS-1-8 Randomized Approximation Scheme for Estimating Critical Path Length of Stochastic PERT Network
- 0.935-Approximation Randomized Algorithm for MAX 2SAT and Its Derandomization
- NEW APPROXIMATION ALGORITHMS FOR MAX 2SAT AND MAX DICUT
- Note on Equitable Round-Robin Tournaments
- A SURVEY OF ALGORITHMS FOR CALCULATING POWER INDICES OF WEIGHTED MAJORITY GAMES
- Is a Given Flow Uncontrollable? (Special Section on Discrete Mathematics and Its Applications)