Geodesic
Optimization of an SMD placement machine and flows in parametric networks
Kybernetika, Tome 47 (2011) no. 5, pp. 722-731

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

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(|F|)$ different target values and so this approach leads to a strongly polynomial algorithm consisting of at most $O(|F|)$ maximum flow computations.
Classification : 05C21, 90B30, 90C27
Keywords: SMD machine optimization; network flow; algorithm 
@article{KYB_2011__47_5_a4,
     author = {Cechl\'arov\'a, Katar{\'\i}na and Fleiner, Tam\'as},
     title = {Optimization of an {SMD} placement machine and flows in parametric networks},
     journal = {Kybernetika},
     pages = {722--731},
     publisher = {mathdoc},
     volume = {47},
     number = {5},
     year = {2011},
     mrnumber = {2850459},
     zbl = {1236.90046},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/KYB_2011__47_5_a4/}
}
TY  - JOUR
AU  - Cechlárová, Katarína
AU  - Fleiner, Tamás
TI  - Optimization of an SMD placement machine and flows in parametric networks
JO  - Kybernetika
PY  - 2011
SP  - 722
EP  - 731
VL  - 47
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/KYB_2011__47_5_a4/
LA  - en
ID  - KYB_2011__47_5_a4
ER  - 
%0 Journal Article
%A Cechlárová, Katarína
%A Fleiner, Tamás
%T Optimization of an SMD placement machine and flows in parametric networks
%J Kybernetika
%D 2011
%P 722-731
%V 47
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/KYB_2011__47_5_a4/
%G en
%F KYB_2011__47_5_a4
Cechlárová, Katarína; Fleiner, Tamás. Optimization of an SMD placement machine and flows in parametric networks. Kybernetika, Tome 47 (2011) no. 5, pp. 722-731. http://geodesic.mathdoc.fr/item/KYB_2011__47_5_a4/