Geodesic property of greedy algorithms for optimization problems on jump systems and delta-matroids

DOI10.1016/j.dam.2023.11.003arXiv2206.10439OpenAlexW4388580653MaRDI QIDQ6180564

Norito Minamikawa

Publication date: 22 December 2023

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

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

zbMATH Keywords

greedy algorithmdelta-matroidjump systemgeodesic property

Mathematics Subject Classification ID

Convex programming (90C25) Integer programming (90C10)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An algorithm for \((n-3)\)-connectivity augmentation problem: jump system approach
• Convexity and Steinitz's exchange property
• \(\Delta\)-matroid and jump system
• Some combinatorial properties of discriminants in metric vector spaces
• Pseudomatroids
• Discrete convex analysis
• The membership problem in jump systems
• Exact bounds for steepest descent algorithms of $L$-convex function minimization
• Matching, matroids, and extensions
• A note on M-convex functions on jump systems
• Submodular functions and optimization.
• Polynomial-Time Algorithms for Linear and Convex Optimization on Jump Systems
• Minconvex Factors of Prescribed Size in Graphs
• The Greedy Procedure for Resource Allocation Problems: Necessary and Sufficient Conditions for Optimality
• Greedy algorithm and symmetric matroids
• A GREEDY ALGORITHM FOR MINIMIZING A SEPARABLE CONVEX FUNCTION OVER A FINITE JUMP SYSTEM
• Discrete Convex Analysis
• Delta-Matroids, Jump Systems, and Bisubmodular Polyhedra
• M-Convex Function Minimization Under L1-Distance Constraint and Its Application to Dock Reallocation in Bike-Sharing System
• M-Convex Functions on Jump Systems: A General Framework for Minsquare Graph Factor Problem
• Matroids and the greedy algorithm
• Integer Programming and Combinatorial Optimization

This page was built for publication: Geodesic property of greedy algorithms for optimization problems on jump systems and delta-matroids