Polygon scheduling

Autor(en): Hurink, J
Stichwörter: cyclic scheduling; EVENTS; Mathematics; Mathematics, Applied
Erscheinungsdatum: 1996
Herausgeber: ELSEVIER SCIENCE BV
Journal: DISCRETE APPLIED MATHEMATICS
Volumen: 70
Ausgabe: 1
Startseite: 37
Seitenende: 55
Zusammenfassung: 
Consider a set of circles of the same length and r irregular polygons with vertices on a circle of this length. Each of the polygons has to be arranged on a given subset of all circles and the positions of the polygon on the different circles are depending on each other. How should the polygons be arranged relative to each other to minimize some criterion function depending on the distances between adjacent vertices on all circles? A decomposition of the set of all arrangements of the polygons into local regions in which the optimization problem is convex is given. An exact description of the local regions and a sharp bound on the number of local regions are derived. For the criterion functions minimizing the maximum weighted distance, maximizing the minimum weighted distance, and minimizing the sum of weighted distances the local optimization problems can be reduced to polynomially solvable network flow problems.
ISSN: 0166218X
DOI: 10.1016/0166-218X(95)00100-6

Show full item record

Page view(s)

1
Last Week
0
Last month
1
checked on Feb 22, 2024

Google ScholarTM

Check

Altmetric