Polynomial-Time Algorithms for Linear and Convex Optimization on Jump Systems

DOI10.1137/060656899zbMath1155.90010OpenAlexW2074891551WikidataQ126246767 ScholiaQ126246767MaRDI QIDQ3503231

Akiyoshi Shioura, Ken'ichiro Tanaka

Publication date: 22 May 2008

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/0f5bb722311ca9adbead1f4e71f306844ef9efa1

zbMATH Keywords

polynomial-time algorithmjump systemdiscrete convex functionbisubmodular functionbisubmodular polyhedron

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Convex programming (90C25) Integer programming (90C10) Combinatorial optimization (90C27)

Related Items

Triangle-free 2-matchings and M-concave functions on jump systems ⋮ An algorithm for \((n-3)\)-connectivity augmentation problem: jump system approach ⋮ Geodesic property of greedy algorithms for optimization problems on jump systems and delta-matroids ⋮ A simple algorithm for finding a maximum triangle-free \(2\)-matching in subcubic graphs ⋮ Recent Developments in Discrete Convex Analysis ⋮ A proof of Cunningham's conjecture on restricted subgraphs and jump systems ⋮ A note on M-convex functions on jump systems ⋮ Even factors, jump systems, and discrete convexity