Polynomial-Time Algorithms for Linear and Convex Optimization on Jump Systems
From MaRDI portal
Publication:3503231
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
polynomial-time algorithmjump systemdiscrete convex functionbisubmodular functionbisubmodular polyhedron
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