Shifted matroid optimization

DOI10.1016/J.ORL.2016.05.013MaRDI QIDQ1694792zbMATH OpenOpenAlexFDO

Authors Asaf Levin, Shmuel Onn

Publication date 6 February 2018

Published in Operations Research Letters (Search for Journal in Brave)

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

zbMATH Keywords

combinatorial optimizationinteger programmingmatchingmatroidspanning treeunimodular

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35) Matching models (91B68)

Abstract: We show that finding lexicographically minimal $n$ bases in a matroid can be done in polynomial time in the oracle model. This follows from a more general result that the shifted problem over a matroid can be solved in polynomial time as well.

Recommendations

• scientific article; zbMATH DE number 863480
• Convex Matroid Optimization
• scientific article; zbMATH DE number 4027489
• Matroids and combinatorial optimisation
• Matroid optimization with generalized constraints
• A parameterized view on matroid optimization problems
• A Parameterized View on Matroid Optimization Problems
• scientific article; zbMATH DE number 3946155

Cites work

• Approximate nonlinear optimization over weighted independence systems
• Common transversals and strong exchange systems
• Disjoint Common Transversals and Exchange Structures
• scientific article; zbMATH DE number 3862930 (Why is no real title available?)
• scientific article; zbMATH DE number 3628712 (Why is no real title available?)
• Nonlinear discrete optimization. An algorithmic theory
• Nonlinear Matroid Optimization and Experimental Design
• Parametric nonlinear discrete optimization over well-described sets and matroid intersections
• The NP-Completeness of Edge-Coloring
• The unimodular intersection problem

Cited in

(4)

• Decreasing minimization on M-convex sets: background and structures
• Decreasing minimization on M-convex sets: algorithms and applications
• Approximate separable multichoice optimization over monotone systems
• Optimization over degree sequences

This page was built for publication: Shifted matroid optimization

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