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/2007
Entry Accepted: 06/18/2007
Entry Last Modified: 06/18/2007

Modify/Update this entry