A strongly polynomial method for solving integer max-linear optimization problems in a generic case

Research output: Contribution to journalArticlepeer-review

Authors

Colleges, School and Institutes

Abstract

We study the existence of integer solutions to max-linear optimization problems. Specifically, we show that, in a generic case, the integer max-linear optimization problem can be solved in strongly polynomial time. This extends results from our previous papers where polynomial methods for this generic case were given.

Details

Original languageEnglish
Pages (from-to)941-963
Number of pages23
JournalJournal of Optimization Theory and Applications
Volume165
Issue number3
Early online date24 Jun 2014
Publication statusPublished - 2015

Keywords

  • Max-linear optimization problem, Integer vector, Max-linear system, 15A80