Semidefinite Programming Based Approaches to Home-Away Assignment Problems in Sports Scheduling

机译：基于半定规划的运动调度中归属分配问题的方法

获取原文

获取原文并翻译 | 示例

页面导航

摘要
著录项
相似文献
相关主题

摘要

For a given schedule of a round-robin tournament and a matrix of distances between homes of teams, an optimal home-away assignment problem is to find a home-away assignment that minimizes the total traveling distance. We propose a technique to transform the problem to MIN RES CUT. We apply Goemans and Williamson's 0.878-approximation algorithm for MAX RES CUT, which is based on a positive semidefinite programming relaxation, to the obtained MIN RES CUT instances. Computational experiments show that our approach quickly generates solutions of good approximation ratios.

机译：对于给定的循环赛赛程和球队两队之间的距离矩阵，最佳的离家出走分配问题是找到使总旅行距离最小的离家出走分配。我们提出了一种将问题转换为MIN RES CUT的技术。对于获得的MIN RES CUT实例，我们将基于正半定编程松弛的Goemans和Williamson的0.878近似算法用于MAX RES CUT。计算实验表明，我们的方法可以快速生成具有良好近似率的解。

著录项

来源
《International Conference on Algorithmic Applications in Management(AAIM 2005); 20050622-25; Xian(CN)》|2005年|P.95-103|共9页
会议地点 Xian(CN)
作者
Ayami Suzuka; Ryuhei Miyashiro; Akiko Yoshise; Tomomi Matsui;
展开▼
作者单位

Graduate School of Systems and Information Engineering, University of Tsukuba, Tsukuba, Ibaraki 305-8573, Japan;

展开▼
会议组织
原文格式 PDF
正文语种 eng
中图分类计算技术、计算机技术;
关键词
sports timetabling; semidefinite programming; goemans and williamson's approximation algorithm;

机译：体育时间表；半定规划； goemans和williamson的近似算法;

相似文献

外文文献
中文文献
专利

1. Dependent Randomized Rounding to the Home-Away Assignment Problem in Sports Scheduling [J] . Ayami SUZUKA, Ryuhei MIYASHIRO, Akiko YOSHISE, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences . 2006,第5期

机译：运动调度中归属分配问题的相关随机四舍五入
2. A Reduced Semidefinite Programming Formulation for HA Assignment Problems in Sport Scheduling [J] . H. J.?LARA, A.S.?SIQUEIRA, J.?YUAN TEMA (So Carlos) . 2018,第3期

机译：运动调度中高可用性分配问题的简化半定规划公式
3. Modelling public transport on-board congestion: comparing schedule-based and agent-based assignment approaches and their implications [J] . Cats Oded, Hartl Maximilian Journal of Advanced Transportation . 2016,第6期

机译：对公共交通工具上的交通拥堵进行建模：比较基于时间表和基于代理的分配方法及其含义
4. Semidefinite Programming Based Approaches to Home-Away Assignment Problems in Sports Scheduling [C] . Ayami Suzuka, Ryuhei Miyashiro, Akiko Yoshise, International Conference on Algorithmic Applications in Management . 2005

机译：基于SMITION的基于SEMIDIFINITE编程的体育计划中的家庭分配问题的方法
5. Algorithmic and mathematical programming approaches to scheduling problems with energy-based objectives. [D] . Fang, Kan. 2013

机译：用算法和数学编程方法来计划基于能量目标的问题。
6. Efficient classification of complete parameter regions based on semidefinite programming [O] . Lars Kuepfer, Uwe Sauer, Pablo A Parrilo 2007

机译：基于半定规划的完整参数区域有效分类
7. Semidefinite programming based approaches to home-away assignment problems in sports scheduling [O] . Suzuka Ayami, Miyashiro Ryuhei, Yoshise Akiko, 2005

机译：运动调度中基于半定规划的无家可归问题的解决方法

Semidefinite Programming Based Approaches to Home-Away Assignment Problems in Sports Scheduling

摘要

著录项

相似文献

相关主题

期刊订阅