University of Birmingham > Talks@bham > Optimisation and Numerical Analysis Seminars > On tropical linear and integer programs

## On tropical linear and integer programsAdd to your list(s) Download to your calendar using vCal - Peter Butkovic (University of Birmingham)
- Thursday 23 February 2017, 12:00-13:00
- University House, 110.
If you have a question about this talk, please contact Sergey Sergeev. We present simple compact proofs of the strong and weak duality theorems of tropical linear programming. It follows that there is no duality gap for a pair of tropical primal-dual problems. This result together with known properties of subeigenvectors enables us to directly solve a special tropical linear program with two-sided constraints. We also study the duality gap in tropical integer linear programming. A direct solution is available for the primal problem. An algorithm of quadratic complexity is presented for the dual problem. A direct solution is available provided that all coefficients of the objective function are integer. This solution provides a good estimate of the optimal objective function value in the general case. This talk is part of the Optimisation and Numerical Analysis Seminars series. ## This talk is included in these lists:Note that ex-directory lists are not shown. |
## Other listsComputer Science Distinguished Seminar Bravo PIPS - Postgraduate Informal Physics Seminars## Other talksHydrodynamics and Chaos in Quantum Matter RSC 2019 Dalton Emerging Researcher Award Lecture School Seminar EV Charging Security at the Physical-Layer Fenchel Duality Theory and a Primal-Dual Algorithm on Riemannian Manifolds Periodic PDEs with critical contrast: unified approach to homogenisation and links to time-dispersive media (Joint Analysis / Applied Mathematics Seminar) |