The width and integer optimization on simplices with bounded minors of the constraint matrices

被引：7
|
作者：
Gribanov, D. V. [1 ,2 ]
Chirkov, A. Y. [1 ]
机构：
[1] Lobachevsky State Univ Nizhny Novgorod, 23 Gagarina Ave, Nizhnii Novgorod 603950, Russia
[2] Natl Res Univ Higher Sch Econ, 136 Rodionova, Nizhnii Novgorod 603093, Russia
来源：
OPTIMIZATION LETTERS | 2016年 / 10卷 / 06期
基金：
俄罗斯基础研究基金会;
关键词：
Integer programming; Polytope; Unimodular decomposition; Width; Flatness theorem; Matrix minors; Efficient algorithm; NONSYMMETRIC CONVEX-BODIES;
D O I：
10.1007/s11590-016-1048-y
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
In this paper, we will show that the width of simplices defined by systems of linear inequalities can be computed in polynomial time if some minors of their constraint matrices are bounded. Additionally, we present some quasi-polynomial-time and polynomial-time algorithms to solve the integer linear optimization problem defined on simplices minus all their integer vertices assuming that some minors of the constraint matrices of the simplices are bounded.
引用
收藏
页码：1179 / 1189
页数：11
相关论文
共 50 条
  • [1] The width and integer optimization on simplices with bounded minors of the constraint matrices
    D. V. Gribanov
    A. Y. Chirkov
    Optimization Letters, 2016, 10 : 1179 - 1189
  • [2] The computational complexity of dominating set problems for instances with bounded minors of constraint matrices
    Malyshev, D. S.
    Gribanov, D., V
    DISCRETE OPTIMIZATION, 2018, 29 : 103 - 110
  • [3] The computational complexity of three graph problems for instances with bounded minors of constraint matrices
    Gribanov, D. V.
    Malyshev, D. S.
    DISCRETE APPLIED MATHEMATICS, 2017, 227 : 13 - 20
  • [4] On bounded ratios of minors of totally positive matrices
    Soskin, Daniel
    Gekhtman, Michael
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2025, 715 : 46 - 67
  • [5] Constraint Satisfaction Problems of Bounded Width
    Barto, Libor
    Kozik, Marcin
    2009 50TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE: FOCS 2009, PROCEEDINGS, 2009, : 595 - 603
  • [6] On generators of bounded ratios of minors for totally positive matrices
    Boocher, Adam
    Froehle, Bradley
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2008, 428 (07) : 1664 - 1684
  • [7] Ka,k minors in graphs of bounded tree-width
    Böhme, T
    Maharry, J
    Mohar, B
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2002, 86 (01) : 133 - 147
  • [8] On integer programming and the branch-width of the constraint matrix
    Cunningham, William H.
    Geelen, Jim
    INTEGER PROGRAMMING AND COMBINATORIAL OPTIMIZATION, PROCEEDINGS, 2007, 4513 : 158 - +
  • [9] Skew-adjacency matrices of tournaments with bounded principal minors
    Boussairi, Abderrahim
    Ezzahir, Sara
    Lakhlifi, Soufiane
    Mahzoum, Soukaina
    DISCRETE MATHEMATICS, 2023, 346 (10)
  • [10] RELIABILITY OPTIMIZATION WITH INTEGER CONSTRAINT COEFFICIENTS
    MISRA, KB
    SHARMA, J
    MICROELECTRONICS AND RELIABILITY, 1973, 12 (05): : 431 - 433
12345