BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.bham.ac.uk//v3//EN
BEGIN:VEVENT
CATEGORIES:Optimisation and Numerical Analysis Seminars
SUMMARY:Tropical Mathematics and Combinatorial Optimisatio
n - Peter Butkovic (School of Mathematics\, Univer
sity of Birmingham)
DTSTART:20171109T120000Z
DTEND:20171109T130000Z
UID:TALK2914AT
URL:/talk/index/2914
DESCRIPTION:Tropical mathematics has emerged as a new\, unconv
entional modelling and solution tool for a variety
of theoretical and practical problems ranging fro
m computer science\, biology and phylogenetic to p
roduction scheduling\, railway scheduling and cryp
tography. \n\nWe will present a selection of links
between tropical mathematics and combinatorial op
timisation indicating potential of tropical method
ology for combinatorial optimisation problems. The
se will include: \n\n1. Interpretation of the maxi
mum cycle mean in a directed graph as a key concep
t in the tropical spectral theory. This enables us
to easily and straightforwardly derive some formu
lae such as the maximum cycle mean of a matrix pow
er.\n\n2. Usual longest/shortest distances matrix
can be found by a repeated tropical squaring of th
e direct distances matrix.\n\n3. Efficient descrip
tion of the complete solution set to a system of d
ual (Afriat) inequalities. This provides a tool fo
r finding solutions satisfying specific requiremen
ts such as integrality.\n\n4. Efficient descriptio
n of the Hungarian (assignment problem) scaling wh
ich\, in addition to the usual scaling\, enables u
s to strictly visualize AP-active entries.\n\n5. O
ptimal assignment problem value coincides with the
tropical permanent of a matrix\, which (due to th
e absence of subtraction) assumes the role of a de
terminant and becomes a tool for analysing systems
of tropical equations and tropical linear indepen
dence\, with uniqueness and parity of optimal perm
utations playing a key role. In this respect new v
ariants of the classical assignment problem of unr
esolved computational complexity have been introdu
ced (parity assignment problem\, best AP principal
submatrix problem). \n
LOCATION:LTB Watson
CONTACT:Sergey Sergeev
END:VEVENT
END:VCALENDAR