A scaling algorithm for optimizing arbitrary functions over vertices of polytopes

DOI10.1007/S10107-020-01522-0zbMATH Open1478.90104OpenAlexW3033549885MaRDI QIDQ2235141FDOQ2235141

Authors: Sergei Chubanov 

Publication date: 20 October 2021

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-020-01522-0

Recommendations

• scientific article; zbMATH DE number 2086909
• Scaling: A general framework
• A Faster Scaling Algorithm for Minimizing Submodular Functions
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.

zbMATH Keywords

nonlinear optimizationgreedy algorithmdiameterscalingsimplex methodbinary optimization

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cites Work

• On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds--Karp to Bland and Beyond
• On the diameter of convex polytopes
• The Hirsch conjecture is true for (0,1)-polytopes
• An application of simultaneous diophantine approximation in combinatorial optimization
• Random walks, totally unimodular matrices, and a randomised dual simplex algorithm
• A bound for the number of different basic solutions generated by the simplex method
• Approximate Local Search in Combinatorial Optimization
• 0/1-Integer programming: Optimization and Augmentation are equivalent
• On the relative complexity of 15 problems related to~0/1-integer programming
• A generalized simplex method for integer problems given by verification oracles

Cited In (1)

• Scalable Minimizing-Operators on Polyhedra via Parametric Linear Programming

This page was built for publication: A scaling algorithm for optimizing arbitrary functions over vertices of polytopes

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