  


Minimum weight tcomposition of an integer
Domingos M. Cardoso(dcardosomat.ua.pt) Abstract: If $p \geq t$ are positive integers, a tcomposition of p is an ordered ttuple of positive integers summing p. If $T=(s_1, s_2, \dots, s_t)$ is a tcomposition of p and W is a $p(t1) \times t$ matrix, call $W(T)= \sum_{k=1}^t w_{s_k k}$ the weight of the tcomposition T. We show that finding a minimum weight tcomposition 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/I17, Universidade de Aveiro, 2007. Download: [Postscript][PDF] Entry Submitted: 06/18/2007 Modify/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  