Optimization of an SMD placement machine and flows in parametric networks

Cechlárová, Katarína, and Fleiner, Tamás. "Optimization of an SMD placement machine and flows in parametric networks." Kybernetika 47.5 (2011): 722-731. <http://eudml.org/doc/197097>.

@article{Cechlárová2011,
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(|F|)$ different target values and so this approach leads to a strongly polynomial algorithm consisting of at most $O(|F|)$ maximum flow computations.},
author = {Cechlárová, Katarína, Fleiner, Tamás},
journal = {Kybernetika},
keywords = {SMD machine optimization; network flow; algorithm; algorithm; SMD machine optimization; network flow; algorithm},
language = {eng},
number = {5},
pages = {722-731},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Optimization of an SMD placement machine and flows in parametric networks},
url = {http://eudml.org/doc/197097},
volume = {47},
year = {2011},
}

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
PB - Institute of Information Theory and Automation AS CR
VL - 47
IS - 5
SP - 722
EP - 731
AB - 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.
LA - eng
KW - SMD machine optimization; network flow; algorithm; algorithm; SMD machine optimization; network flow; algorithm
UR - http://eudml.org/doc/197097
ER -