Universität zu Köln

Jünger, Michael and Mallach, Sven ORCID: 0000-0001-5335-0678 (2013). Solving the Simple Offset Assignment Problem as a Traveling Salesman. In: M-SCOPES '13: Proceedings of the 16th International Workshop on Software and Compilers for Embedded Systems, pp. 31-39. ACM.

Preview

PDF preprint2.pdf - Draft Version Download (204kB) | Preview

Abstract

In this paper, we present an exact approach to the Simple Offset Assignment problem arising in the domain of address code generation for digital signal processors. It is based on transformations to weighted Hamiltonian cycle problems and integer linear programming. To the best of our knowledge, it is the first approach capable to solve all instances of the established OffsetStone benchmark set to optimality within reasonable time. Therefore, it enables to evaluate the quality of several heuristics relative to the optimum solutions for the first time. Further, using the same transformations, we present a simple and effective improvement heuristic. In addition, we include an existing heuristic into our experiments that has so far not been evaluated with OffsetStone.

Item Type:	Book Section, Proceedings Item or annotation in a legal commentary
Creators:	Creators Email ORCID ORCID Put Code Jünger, Michael UNSPECIFIED UNSPECIFIED UNSPECIFIED Mallach, Sven UNSPECIFIED orcid.org/0000-0001-5335-0678 UNSPECIFIED
URN:	urn:nbn:de:hbz:38-550466
Title of Book:	M-SCOPES '13: Proceedings of the 16th International Workshop on Software and Compilers for Embedded Systems
Page Range:	pp. 31-39
Date:	2013
Publisher:	ACM
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Refereed:	No
URI:	http://kups.ub.uni-koeln.de/id/eprint/55046