Dependent Randomized Rounding to the Home-Away Assignment Problem in Sports Scheduling(<Special Section>Discrete Mathematics and Its Applications)
スポンサーリンク
概要
- 論文の詳細を見る
Suppose that we have a timetable of a round-robin tournament with a number of teams, and distances among their homes. The home-away assignment problem is to find a home-away assignment that minimizes the total traveling distance of the teams. We propose a formulation of the home-away assignment problem as an integer program, and a rounding algorithm based on Bertsimas, Teo and Vohra's dependent randomized rounding method. Computational experiments show that our method quickly generates feasible solutions close to optimal.
- 社団法人電子情報通信学会の論文
- 2006-05-01
著者
-
Matsui Tomomi
University of Tokyo
-
MATSUI Tomomi
Department of Information and System Engineering, Faculty of Science and Engineering, Chuo Universit
-
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
-
SUZUKA Ayami
Graduate School of Systems and Information Engineering, the University of Tsukuba
-
MIYASHIRO Ryuhei
Institute of Symbiotic Science and Technology, Tokyo University of Agriculture and Technology
-
YOSHISE Akiko
Graduate School of Systems and Information Engineering, the University of Tsukuba
-
Suzuka Ayami
Graduate School Of Systems And Information Engineering The University Of Tsukuba
-
Yoshise Akiko
Graduate School Of Systems And Information Engineering The University Of Tsukuba
-
Matsui Tomomi
Department Of Information And System Engineering Faculty Of Science And Engineering Chuo University
-
Miyashiro Ryuhei
Institute Of Symbiotic Science And Technology Tokyo University Of Agriculture And Technology
-
Matsui Tomomi
Department Of Mathematical Informatics Graduate School Of Information Science And Technology The Uni
-
Miyashiro Ryuhei
Institute of Engineering Tokyo University of Agriculture and Technology
関連論文
- LINEAR TIME APPROXIMATION ALGORITHM FOR MULTICOLORING LATTICE GRAPHS WITH DIAGONALS
- Improved Approximation Algorithms for Firefighter Problem on Trees
- 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
- Optimization of alignment in semiconductor lithography equipment
- Is a Given Flow Uncontrollable? (Special Section on Discrete Mathematics and Its Applications)
- Optimization of Assignment of Rapid Train Stops: Example of the JR Nambu Line
- 3C2 INVERSE ASSIGNMENT PROBLEM FOR TIMETABLING IN TUTORING SCHOOL(Technical session 3C: OS2: Timetabling and assignment problems(2))
- 2C2 OPTIMAL ASSIGNMENT OF RAPID TRAIN STOPS : EXAMPLE OF THE JR NAMBU LINE(Technical session 2C: OS2: Timetabling and assignment problems(1))
- Radiographic Progression of Silicosis among Japanese Tunnel Workers in Kochi