Darts and hoopla board design

被引：7

作者：

Curtis, SA ^{[1
]}

机构：

[1] Oxford Brookes Univ, Dept Comp, Oxford OX33 1HX, England

来源：

INFORMATION PROCESSING LETTERS | 2004年 / 92卷 / 01期

关键词：

algorithms; combinatorial problems; travelling salesman;

D O I：

10.1016/j.ipl.2004.06.005

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

Dartboard design can be seen as an instance of the travelling salesman problem with maximum costs. This paper presents a simple yet optimal greedy algorithm to arrange numbers on both circular dartboards and linear hoopla boards. As a result, it identifies a class of polynomially solvable travelling salesman problems. (C) 2004 Elsevier B.V. All rights reserved.

引用

页码：53 / 56

页数：4

共 6 条

[1]

[Anonymous], MATH GAZETTE

[2] SOME NEW BRANCHING AND BOUNDING CRITERIA FOR THE ASYMMETRIC TRAVELING SALESMAN PROBLEM [J].

CARPANETO, G ;

TOTH, P .

MANAGEMENT SCIENCE, 1980, 26 (07) :736-743

[3] ARRANGING N-DISTINCT NUMBERS ON A LINE OR A CIRCLE TO REACH EXTREME TOTAL VARIATIONS [J].

CHAO, CC ;

LIANG, WQ .

EUROPEAN JOURNAL OF COMBINATORICS, 1992, 13 (05) :325-334

[4]

COHEN GL, 2001, ELECTRON J COMB, V8, pR4

[5]

EISELT HA, 1991, J OPER RES SOC, V42, P113, DOI 10.2307/2583175

[6]

SINGMASTER D., 1980, B I MATH ITS APPL, V16, P93

← 1 →