Uniform and monotone line sum optimization

DOI10.1016/J.DAM.2021.04.008MaRDI QIDQ2028097zbMATH OpenOpenAlexFDO

Authors Martin Koutecký, Shmuel Onn

Publication date 31 May 2021

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

column sumdegree sequencemajorizationmatrixrow sum

Mathematics Subject Classification ID

Vertex degrees (05C07) Combinatorial optimization (90C27)

Abstract: The {em line sum optimization problem} asks for a $(0,1)$-matrix minimizing the sum of given functions evaluated at its row and column sums. We show that the {em uniform} problem, with identical row functions and identical column functions, and the {em monotone} problem, over matrices with nonincreasing row and column sums, are polynomial time solvable.

Recommendations

• Convexification and monotone optimization
• scientific article; zbMATH DE number 3947995
• Unicity in linear optimization
• Convex optimization and monotonic variational inequalities
• Linear optimization with cones of moments and nonnegative polynomials
• Optimization of linear-convex programs
• Practical piecewise-linear approximation for monotropic optimization
• Efficiency and the uniform linear minorization of convex functions
• scientific article; zbMATH DE number 27648
• scientific article; zbMATH DE number 3273621

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?)
• scientific article; zbMATH DE number 3862930 (Why is no real title available?)
• Inequalities: theory of majorization and its applications
• Minconvex Factors of Prescribed Size in Graphs
• On line sum optimization
• Optimization over degree sequences
• Optimization over degree sequences of graphs

Cited in

(3)

• On line sum optimization
• Degree sequence optimization in bounded treewidth
• Degree sequence optimization and extremal degree enumerators

This page was built for publication: Uniform and monotone line sum optimization

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