Paper Info
Title
Optimization of an SMD placement machine and flows in parametric networks.
Abstract
In the minimization of the number of subtours made by the insertion head of an SMD placement machine a variant of the network flow problem arose. In a network with n vertices and m arcs a set F of arcs (parametrized arcs) is given. The task is to find a flow of a given size such that the maximum of flow values along the arcs from F is minimized. This problem can be solved by a sequence of maximum flow computations in modified networks where the capacities of the parametrized arcs are successively set to an increasing sequence of target parameter values. We show that it suffices to consider at most O(vertical bar F vertical bar) different target values and so this approach leads to a strongly polynomial algorithm consisting of at most O(vertical bar F vertical bar) maximum flow computations.
Year
Venue
Keywords
2011
KYBERNETIKA
SMD machine optimization,network flow,algorithm
Field
DocType
Volume
Lead (electronics),Mathematical optimization,Parametric statistics,Mathematics
Journal
47
Issue
ISSN
Citations 
5
0023-5954
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Katarína Cechlárová122628.02
Tamás Fleiner224127.45