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

DOI10.1137/060656899MaRDI QIDQ3503231zbMATH OpenOpenAlexWikidataFDO

Authors 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

bisubmodular functionbisubmodular polyhedrondiscrete convex functionjump systempolynomial-time algorithm

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 953034
• A GREEDY ALGORITHM FOR MINIMIZING A SEPARABLE CONVEX FUNCTION OVER A FINITE JUMP SYSTEM
• scientific article; zbMATH DE number 437553
• On Linear-Time Deterministic Algorithms for Optimization Problems in Fixed Dimension
• Polynomial time algorithms for some classes of constrained nonconvex quadratic problems
• scientific article; zbMATH DE number 5252628
• Strong polyhedral approximation of simple jump sets
• Convex optimization: algorithms and complexity
• A polynomial-time descent method for separable convex optimization problems with linear constraints
• scientific article; zbMATH DE number 617915

Cited in

(16)

• A note on M-convex functions on jump systems
• Even factors, jump systems, and discrete convexity
• Recent developments in discrete convex analysis
• Triangle-free 2-matchings and M-concave functions on jump systems
• An algorithm for \((n-3)\)-connectivity augmentation problem: jump system approach
• A simple algorithm for finding a maximum triangle-free 2-matching in subcubic graphs
• A GREEDY ALGORITHM FOR MINIMIZING A SEPARABLE CONVEX FUNCTION OVER A FINITE JUMP SYSTEM
• A proof of Cunningham's conjecture on restricted subgraphs and jump systems
• scientific article; zbMATH DE number 2115730 (Why is no real title available?)
• Operations on M‐Convex Functions on Jump Systems
• M-Convex Functions on Jump Systems: A General Framework for Minsquare Graph Factor Problem
• Neighbor systems, jump systems, and bisubmodular polyhedra
• Neighbor systems, jump systems, and bisubmodular polyhedra
• Geodesic property of greedy algorithms for optimization problems on jump systems and delta-matroids
• Finding a maximum restricted t-matching via Boolean edge-CSP
• Finding a maximum restricted \(t\)-matching via Boolean edge-CSP

This page was built for publication: Polynomial-Time Algorithms for Linear and Convex Optimization on Jump Systems

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