Cyclic schedules for r irregularly occurring event

P. Brucker, R. Burkard, Johann L. Hurink

Research output: Contribution to journalArticleAcademicpeer-review

16 Citations (Scopus)
48 Downloads (Pure)

Abstract

Consider r irregular polygons with vertices on some circle. Authors explains how the polygons should be arranged to minimize some criterion function depending on the distances between adjacent vertices. A solution of this problem is given. It is based on a decomposition of the set of all schedules into local regions in which the optimization problem is convex. For the criterion functions minimize the maximum distance and maximize the minimum distance the local optimization problems are related to network flow problems which can be solved efficiently. If the sum of squared distances is to be minimized a locally optimal solution can be found by solving a system of linear equations. For fixed r the global problem is polynomially solvable for all the above-mentioned objective functions. In the general case, however, the global problem is NP-hard.
Original languageEnglish
Pages (from-to)173-189
Number of pages17
JournalJournal of computational and applied mathematics
Volume30
Issue number2
DOIs
Publication statusPublished - 28 May 1990
Externally publishedYes

Fingerprint Dive into the research topics of 'Cyclic schedules for r irregularly occurring event'. Together they form a unique fingerprint.

Cite this