- Minimum weight t-composition of an integer Domingos M. Cardoso(dcardosomat.ua.pt) J. Orestes Cerdeira(orestesisa.utl.pt) Abstract: If $p \geq t$ are positive integers, a t-composition of p is an ordered t-tuple of positive integers summing p. If $T=(s_1, s_2, \dots, s_t)$ is a t-composition of p and W is a $p-(t-1) \times t$ matrix, call $W(T)= \sum_{k=1}^t w_{s_k k}$ the weight of the t-composition T. We show that finding a minimum weight t-composition of p reduces to the determination of a shortest path in a certain digraph with O(tp) vertices. This study was motivated by a problem arising from the automobile industry, and the presented result is useful when dealing with huge location problems. Keywords: compositions of integers, graphs, location problems, combinatorial optimization Category 1: Combinatorial Optimization Citation: Cadernos de Matemática, CM07/I-17, Universidade de Aveiro, 2007. Download: [Postscript][PDF]Entry Submitted: 06/18/2007Entry Accepted: 06/18/2007Entry Last Modified: 06/18/2007Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.