On the integer max-linear programming problem

Peter Butkovic; Marie MacCaig

doi:10.1016/j.dam.2013.08.007

On the integer max-linear programming problem

Peter Butkovic, Marie MacCaig

Mathematics

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

9 Citations (Scopus)

179 Downloads (Pure)

Abstract

Max-linear programs have been used to describe optimisation problems for multiprocessor interactive systems. In some instances the variables used in this model are required to be integer; however, no method seems to exist for finding integer solutions to max-linear programs.

For a generic class of matrices, we show that integer solutions to two-sided max-linear systems and programs can be found in polynomial time. For general matrices, we adapt the existing methods for finding real solutions to obtain algorithms for finding integer solutions.

Original language	English
Pages (from-to)	128–141
Journal	Discrete Applied Mathematics
Volume	162
Early online date	13 Sept 2013
DOIs	https://doi.org/10.1016/j.dam.2013.08.007
Publication status	Published - 10 Jan 2014

Keywords

Max-linear system
Integer vector
Max-linear program

Access to Document

10.1016/j.dam.2013.08.007

Butkovic_Integer_max_linear_Discrete_Applied_Mathematics_2014
Eligibility for repository : checked 02/04/2014
Final published version, 446 KBLicence: Creative Commons: Attribution (CC BY)

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{e17530e0ef974e3a84649e2b5d4cbe9f,

title = "On the integer max-linear programming problem",

abstract = "Max-linear programs have been used to describe optimisation problems for multiprocessor interactive systems. In some instances the variables used in this model are required to be integer; however, no method seems to exist for finding integer solutions to max-linear programs.For a generic class of matrices, we show that integer solutions to two-sided max-linear systems and programs can be found in polynomial time. For general matrices, we adapt the existing methods for finding real solutions to obtain algorithms for finding integer solutions.",

keywords = "Max-linear system, Integer vector, Max-linear program",

author = "Peter Butkovic and Marie MacCaig",

year = "2014",

month = jan,

day = "10",

doi = "10.1016/j.dam.2013.08.007",

language = "English",

volume = "162",

pages = "128–141",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier",

}

TY - JOUR

T1 - On the integer max-linear programming problem

AU - Butkovic, Peter

AU - MacCaig, Marie

PY - 2014/1/10

Y1 - 2014/1/10

N2 - Max-linear programs have been used to describe optimisation problems for multiprocessor interactive systems. In some instances the variables used in this model are required to be integer; however, no method seems to exist for finding integer solutions to max-linear programs.For a generic class of matrices, we show that integer solutions to two-sided max-linear systems and programs can be found in polynomial time. For general matrices, we adapt the existing methods for finding real solutions to obtain algorithms for finding integer solutions.

AB - Max-linear programs have been used to describe optimisation problems for multiprocessor interactive systems. In some instances the variables used in this model are required to be integer; however, no method seems to exist for finding integer solutions to max-linear programs.For a generic class of matrices, we show that integer solutions to two-sided max-linear systems and programs can be found in polynomial time. For general matrices, we adapt the existing methods for finding real solutions to obtain algorithms for finding integer solutions.

KW - Max-linear system

KW - Integer vector

KW - Max-linear program

U2 - 10.1016/j.dam.2013.08.007

DO - 10.1016/j.dam.2013.08.007

M3 - Article

SN - 0166-218X

VL - 162

SP - 128

EP - 141

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

On the integer max-linear programming problem

Abstract

Keywords

Access to Document

Fingerprint

Projects

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

Cite this