On the integer max-linear programming problem

被引：15

作者：

Butkovic, Peter ^{[1
]}

MacCaig, Marie ^{[1
]}

机构：

[1] Univ Birmingham, Sch Math, Birmingham B15 2TT, W Midlands, England

来源：

DISCRETE APPLIED MATHEMATICS | 2014年 / 162卷

基金：

英国工程与自然科学研究理事会;

关键词：

Max-linear system; Integer vector; Max-linear program; ALGEBRA;

D O I：

10.1016/j.dam.2013.08.007

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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. (C) 2013 The Authors. Published by Elsevier B.V. All rights reserved.

引用

页码：128 / 141

页数：14

共 12 条

[1] THE TROPICAL DOUBLE DESCRIPTION METHOD [J].