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

P. Butkovic; M. Maccaig

doi:10.1007/s10957-014-0596-5

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

P. Butkovic, M. Maccaig

Mathematics

Research output: Contribution to journal › Article › peer-review

1 Citation (Scopus)

114 Downloads (Pure)

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.

Original language	English
Pages (from-to)	941-963
Number of pages	23
Journal	Journal of Optimization Theory and Applications
Volume	165
Issue number	3
Early online date	24 Jun 2014
DOIs	https://doi.org/10.1007/s10957-014-0596-5
Publication status	Published - 2015

Keywords

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

Access to Document

10.1007/s10957-014-0596-5

Butkovic_Strongly_polynomial_method_Journal_Optimization_Theory_Applications_2014
Eligibility for repository : checked 15/08/2014
Final published version, 257 KBLicence: Creative Commons: Attribution (CC BY)

http://link.springer.com/10.1007/s10957-014-0596-5

Perron-Frobenius Theory and Max-Algebraic Combinatorics of Nonnegative Matrices
Butkovic, P.
Engineering & Physical Science Research Council
12/03/12 → 11/03/14
Project: Research Councils

Cite this

@article{4307a6e0a0ac4251a772511b545e9a7a,

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

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.",

keywords = "Max-linear optimization problem, Integer vector, Max-linear system, 15A80",

author = "P. Butkovic and M. Maccaig",

year = "2015",

doi = "10.1007/s10957-014-0596-5",

language = "English",

volume = "165",

pages = "941--963",

journal = "Journal of Optimization Theory and Applications",

issn = "0022-3239",

publisher = "Springer",

number = "3",

}

TY - JOUR

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

AU - Butkovic, P.

AU - Maccaig, M.

PY - 2015

Y1 - 2015

N2 - 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.

AB - 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.

KW - Max-linear optimization problem

KW - Integer vector

KW - Max-linear system

KW - 15A80

U2 - 10.1007/s10957-014-0596-5

DO - 10.1007/s10957-014-0596-5

M3 - Article

SN - 0022-3239

VL - 165

SP - 941

EP - 963

JO - Journal of Optimization Theory and Applications

JF - Journal of Optimization Theory and Applications

IS - 3

ER -

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

Abstract

Keywords

Access to Document

Fingerprint

Projects

Perron-Frobenius Theory and Max-Algebraic Combinatorics of Nonnegative Matrices

Cite this