# Professor Peter Butkovic

School of Mathematics

Professor of Applied Discrete Mathematics

## Contact details

- Telephone
- +44 (0) 121 414 6600
- Fax
- +44 (0) 121 414 3389
- p.butkovic@bham.ac.uk

- Address
- School of Mathematics

Watson Building

University of Birmingham

Edgbaston

Birmingham

B15 2TT

UK

Professor Butkovic's main research interest is the theory of max-linear systems, rapidly evolving area of numerical linear algebra and applied discrete mathematics. He is the author of a research monograph on this subject and also the author or co-author of more than 50 peer-reviewed papers.

Peter Butkovic has received a number of grants in support of his research, including those from the EPSRC, LMS and Royal Society. He was the Chair of the LMS joint research group on tropical mathematics and its applications.

Peter has been in charge of a variety of modules such as Combinatorial Optimisation, Game Theory, Research Frontiers in Management Mathematics, Linear Programming, Non-Linear Programming and History of Mathematics. He supervises MSci projects and postgraduate students.

More information can be found on http://web.mat.bham.ac.uk/P.Butkovic/

## Qualifications

- PhD Prague 1983

## Biography

Peter Butkovic arrived in Birmingham in 1991 as a lecturer in Combinatorial Optimisation. He joined the research group led by Professor R.A.Cuninghame-Green with whom he enjoyed many years of fruitful collaboration.

Peter was the Principal Investigator of several EPSRC funded research projects in tropical linear algebra and its applications, in particular to multiprocessor interactive systems. He published a monograph on max-linear systems and more than 60 papers. This includes seminal papers on the combinatorial aspects of max-algebra, strong regularity of matrices, on the job rotation problem, robustness of tropical matrices, generalised eigenproblem and max-linear programming. He gave lectures at more than 70 international conferences and seminars. In 2003 he organised an International Workshop on Max-Algebra in Birmingham and more recently three minisymposia on max-algebra for the International Linear Algebra Society and SIAM.

During his appointment in Birmingham he introduced new courses in the School of Mathematics such as Game Theory, Research Frontiers in Management Mathematics and History of Optimisation. He taught Combinatorial Optimisation almost every year between 1991 and 2016. Peter has also designed a number of new undergraduate programmes. He completed 7 postgraduate supervisions and supervised a post-doctoral researcher.

## Teaching

- Single Honours Mathematics (G100, G103, G141)
- Mathematics Majors: Mathematics with Business Management (G1N2)

## Postgraduate supervision

- Tropical linear algebra
- Applications of tropical linear algebra

## Research

**RESEARCH THEMES **

- Tropical linear algebra (current)
- Combinatorial optimisation (past)
- Applied discrete mathematics (past)
- Computational complexity (past)

**RESEARCH ACTIVITY **

- Peter’s research monograph on max-algebra commissioned by Springer was published in September 2010. This book provides an introductory text to max-algebra and presents results on advanced topics. The theory in the first five chapters is self-contained and may be used as support for undergraduate or postgraduate courses. Chapters 6-10 cover more advanced topics with emphasis on feasibility and reachability. The book has been written for a wide-ranging readership, from undergraduate and postgraduate students to researchers and mathematicians working in industry, commerce or management.
- Publication of the seminal paper on max-linear programming in 2010 which created the foundations of a new branch of optimisation and tropical mathematics. It widens the range of applications of max-algebra.
- Polynomial method for narrowing the search for generalised eigenvalues, which is one of the most intractable problems in tropical linear algebra. This method reduces the set of candidates for eigenvalues; in some cases it identifies the whole spectrum.
- (With R. A. Cuninghame-Green) Pseudopolynomial alternating method for solving two-sided max-linear systems.
- Peter was involved in the application of the max-algebraic spectral theory to the diagonal scaling of matrices. It has been proved that max-algebra can be used to efficiently describe all solutions to a class of combinatorial problems. It is one of the results of the EPSRC funded research, achieved in collaboration with Prof. H. Schneider (University of Wisconsin, Madison).
- Criteria for robustness of matrices in max-algebra. These results provide an efficient characterisation of matrices whose orbit will reach an eigenspace with any starting vector. Equivalently, they characterise production matrices for which the production process based on interactively working processors will reach a steady regime independently of starting times.
- Fast method for finding all essential coefficients of a characteristic maxpolynomial. This problem, which finds applications in managerial decision making (it is essentially the so called “job rotation problem”), is of undecided computational complexity. However it was shown that many special cases are efficiently solvable. It is one of the results of Peter’s EPSRC funded research, achieved in collaboration with Prof. R. E. Burkard (Graz University of Technology, Austria).
- (With S. Gaubert and R. A. Cuninghame-Green) Complete solution of the minimal-dimensional realisation (MDR) problem for convex sequences. This result presents a new connection between classical inequalities theory and modern theory of discrete-dynamic systems. MDR for general sequences is a hard, unresolved problem.
- Finding and proving that the solution set of any two-sided max-linear system is finitely generated (1982). This is a theoretical result of fundamental importance cited by many authors. It was discovered well before other researchers attempted to solve the problem.
- Seminal paper on the strong regularity of matrices proving its the equivalence between to the uniqueness of the optimal solution to the assignment problem (1983). This result revealed a link between two seemingly unrelated questions long before it was studied in other research centres worldwide and gave rise to a number of findings.

## Other activities

Associate Editor of Linear Algebra and its Applications (2009 - 2016)

Management of Teaching@

- 2nd year Director
- Director of Joint Honours
- Head of Quality assurance and enhancement
- Peer observation coordinator
- Chair of the Teaching and Learning Committee

Currently he is a Deputy Head of School with responsibilities for new staff

## Publications

### Principal publications:

Butkovič, P. (2010): Max-linear Systems: Theory and Algorithms, Springer Monographs in Mathematics, Springer-Verlag.

P.Butkovic: On integer images of max-plus linear mappings, Discrete Applied Mathematics 239 (2018) 62-74.

P.Butkovic and M.Fiedler: Tropical tensor product (PDF), School of Mathematics, University of Birmingham, preprint 2011/02, arXiv:1805.03174 (2018).

P.Butkovic: On tropical linear and integer programs(PDF), arXiv:1709.08983 (2017).

P.Butkovic and D.Jones: On special cases of the generalized max-plus eigenproblem, SIAM Journal on Matrix Analysis and Applications, Vol.37, No.3 (2016) 1002-1021.

P.Butkovic: On tropical supereigenvectors, Linear Algebra and Its Applications 498 (2016) 574-591.

P.Butkovic, H.Schneider, S.Sergeev and B.-S. Tam: Two cores of a nonnegative matrix, Linear Algebra and its Applications 439 (2013) 1929–1954.

P.Butkovic, M.MacCaig: On integer eigenvectors and subeigenvectors in the max-plus algebra, Linear Algebra and its Applications 438 (2013) 3408–3424.

P.Butkovic, H.Schneider and S.Sergeev: Recognizing weakly stable matrices, SIAM J. Control Optim. 2012, 50(5), 3029-3051.

P.Butkovic and S.Lewis: On the job rotation problem. Discrete Optimization 4 (2007) 163-174.

Butkovič, P., Cuninghame-Green, R.A.and Gaubert, S. (2009), Reducible spectral theory with applications to the robustness of matrices in max-algebra, SIAM Journal on Matrix Analysis and Applications 31(3): 1412-1431

Butkovič, P. and Aminu, A. (2009), Max-linear programming. IMA Journal of Management Mathematics 20(3): 1-17.

Butkovič, P. (2008), Finding a bounded mixed-integer solution to a system of dual inequalities, Operations Research Letters 36: 623-627.

Butkovič, P. and Schneider, H. (2005), Applications of max-algebra to diagonal scaling of matrices, Electronic Journal of Linear Algebra 13: 262-273

Burkard, R.E. and Butkovič, P. (2003), Max algebra and the linear assignment problem, Mathematical Programming, Ser.B 98: 415-429

Cuninghame-Green, R.A. and Butkovič, P. (2003), The equation Ax = By over (max, +), Theoretical Computer Science 293: 3-12

Butkovič, P. (2003), Max-algebra: the linear algebra of combinatorics? Linear Algebra and Its Applications 367: 313-335

Burkard, R.E. and Butkovič, P. (2003), Finding all essential terms of a characteristic maxpolynomial, Discrete Applied Mathematics 130: 367-380

Butkovič, P. (2000), The simple image set of (max, +) linear mappings, Discrete Applied Mathematics 105: 73-86

P.Butkovic: On tropical linear and integer programs, arXiv:1709.08983 (2017).