On the integer max-linear programming problem

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

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2014-01, Vol.162, p.128-141
Main Authors: Butkovič, Peter, MacCaig, Marie
Format: Article
Language:English
Subjects:
Integer vector
Integers
Interactive
Mathematical analysis
Mathematical models
Max-linear program
Max-linear system
Multiprocessor
Optimization
Programming
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2013.08.007