Testing membership in matroid polyhedra
From MaRDI portal
Publication:1056350
DOI10.1016/0095-8956(84)90023-6zbMath0522.90067OpenAlexW2080656989MaRDI QIDQ1056350
Publication date: 1984
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0095-8956(84)90023-6
combinatorial optimizationnetwork flowspolynomial-time algorithmssubmodular functionscomputational membership determinationmatroid partitioning
Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Combinatorial aspects of matroids and geometric lattices (05B35) Polytopes and polyhedra (52Bxx)
Related Items
The recoverable robust spanning tree problem with interval costs is polynomially solvable, A rounding technique for the polymatroid membership problem, Strength of a graph and packing of trees and branchings, Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization, Efficient implementation of Carathéodory's theorem for the single machine scheduling polytope, A LP-based approximation algorithm for generalized traveling salesperson path problem, Submodular Stochastic Probing on Matroids, Comparison of three approaches to studying stability of solutions to problems of discrete optimization and computational geometry, Integral packing of trees and branchings, Decomposition Algorithm for the Single Machine Scheduling Polytope, Layers and matroids for the traveling salesman's paths, New approaches to multi-objective optimization, Analyzing Residual Random Greedy for monotone submodular maximization, An LP-based approximation algorithm for the generalized traveling salesman path problem, Matroid-constrained vertex cover, A push-relabel framework for submodular function minimization and applications to parametric optimization, Graphic Submodular Function Minimization: A Graphic Approach and Applications, Degree bounded matroids and submodular flows, The principal lattice of partitions of a submodular function, Faster algorithms for security games on matroids, On the cardinality constrained matroid polytope, Security games on matroids, A generalized approximation framework for fractional network flow and packing problems, Unnamed Item, A new algorithm for the intersection of a line with the independent set polytope of a matroid, Better \(s-t\)-tours by Gao trees, Maximizing monotone submodular functions over the integer lattice, ON THE PIPAGE ROUNDING ALGORITHM FOR SUBMODULAR FUNCTION MAXIMIZATION — A VIEW FROM DISCRETE CONVEX ANALYSIS, Log-concave polynomials. I: Entropy and a deterministic approximation algorithm for counting bases of matroids, Polyhedra with the integer Carathéodory property, Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal, Facility Location with Matroid or Knapsack Constraints, A combinatorial algorithm minimizing submodular functions in strongly polynomial time., A fully combinatorial algorithm for submodular function minimization., Finding feasible vectors of Edmonds-Giles polyhedra, An integer analogue of Carathéodory's theorem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The ellipsoid method and its consequences in combinatorial optimization
- An unbounded matroid intersection polyhedron
- Blocking, antiblocking, and pairs of matroids and polymatroids
- A Primal-Dual Algorithm for Submodular Flows
- The Partial Order of a Polymatroid Extreme Point
- Minimum cuts, modular functions, and matroid polyhedra
- Preemptive Scheduling with Release Times, Deadlines, and Due Times
- Computing Maximal “Polymatroidal” Network Flows
- Selected Applications of Minimum Cuts in Networks
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
- Minimum partition of a matroid into independent subsets
- Blocking and anti-blocking pairs of polyhedra
