Shifted matroid optimization

DOI10.1016/J.ORL.2016.05.013zbMATH Open1380.90238arXiv1507.00447OpenAlexW2963988918MaRDI QIDQ1694792FDOQ1694792

Shmuel Onn, Asaf Levin

Publication date: 6 February 2018

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

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.

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

zbMATH Keywords

combinatorial optimizationmatchinginteger programmingmatroidspanning treeunimodular

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• The NP-Completeness of Edge-Coloring
• 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)

• Parameterized shifted combinatorial optimization
• Approximate separable multichoice optimization over monotone systems
• Optimization over Degree Sequences
• Decreasing minimization on M-convex sets: background and structures
• Decreasing minimization on M-convex sets: algorithms and applications

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• A parameterized view on matroid optimization problems 👍 👎
• Matroids and Combinatorial Optimisation 👍 👎
• Convex Matroid Optimization 👍 👎
• Matroid optimization with generalized constraints 👍 👎
• A Parameterized View on Matroid Optimization Problems 👍 👎
• Parameterized shifted combinatorial optimization 👍 👎

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)