On line sum optimization

DOI10.1016/J.LAA.2020.10.004MaRDI QIDQ2228118zbMATH OpenOpenAlexFDO

Authors Shmuel Onn

Publication date 16 February 2021

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2012.02617

zbMATH Keywords

column sumdegree sequencegraphmajorizationmatrixrow sum

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Boolean and Hadamard matrices (15B34) Linear optimal control problems (49N05)

Abstract: We show that the {em column sum optimization problem}, of finding a $(0,1)$-matrix with prescribed row sums which minimizes the sum of evaluations of given functions at its column sums, can be solved in polynomial time, either when all functions are the same or when all row sums are bounded by any constant. We conjecture that the more general {em line sum optimization problem}, of finding a matrix minimizing the sum of given functions evaluated at its row sums and column sums, can also be solved in polynomial time.

Recommendations

• Uniform and monotone line sum optimization
• Permuting Elements Within Columns of a Matrix in Order to Minimize Maximum Row Sum
• k-sum optimization problems
• On \(k\)-sum optimization
• On the matrix permutation problem

Cites work

• Combinatorial matrix classes
• Combinatorial Properties of Matrices of Zeros and Ones
• scientific article; zbMATH DE number 3169205 (Why is no real title available?)
• Inequalities: theory of majorization and its applications
• Minconvex Factors of Prescribed Size in Graphs
• Optimization over degree sequences
• Polyhedral proof methods in combinatorial optimization

Cited in

(2)

• Uniform and monotone line sum optimization
• Permuting Elements Within Columns of a Matrix in Order to Minimize Maximum Row Sum

This page was built for publication: On line sum optimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2228118)