Shifted matroid optimization
From MaRDI portal
Publication:1694792
DOI10.1016/J.ORL.2016.05.013zbMATH Open1380.90238arXiv1507.00447OpenAlexW2963988918MaRDI QIDQ1694792FDOQ1694792
Authors: Asaf Levin, Shmuel Onn 
Publication date: 6 February 2018
Published in: Operations Research Letters (Search for Journal in Brave)
Abstract: We show that finding lexicographically minimal 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.
Full work available at URL: https://arxiv.org/abs/1507.00447
Recommendations
- scientific article; zbMATH DE number 863480
- Convex Matroid Optimization
- scientific article; zbMATH DE number 4027489
- Matroids and combinatorial optimisation
- Parameterized shifted combinatorial optimization
- Parameterized shifted combinatorial optimization
- 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
Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Integer programming (90C10) Matching models (91B68)
Cites Work
- Title not available (Why is that?)
- The NP-Completeness of Edge-Coloring
- Title not available (Why is that?)
- Nonlinear discrete optimization. An algorithmic theory
- Parametric nonlinear discrete optimization over well-described sets and matroid intersections
- Approximate nonlinear optimization over weighted independence systems
- Nonlinear Matroid Optimization and Experimental Design
- Disjoint Common Transversals and Exchange Structures
- The unimodular intersection problem
- Common transversals and strong exchange systems
Cited In (5)
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)
