Cyclic schedules for r irregularly occurring event

Share/Save/Bookmark

Brucker, P. and Burkard, R. and Hurink, J.L. (1990) Cyclic schedules for r irregularly occurring event. Journal of Computational and Applied Mathematics, 30 (2). pp. 173-189. ISSN 0377-0427

open access
[img]
Preview
PDF
1MB
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.
Item Type:Article
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/66533
Official URL:http://dx.doi.org/10.1016/0377-0427(90)90026-V
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page