Optimal matroid partitioning problems

DOI10.4230/LIPICS.ISAAC.2017.51MaRDI QIDQ5136271zbMATH OpenFDO

Authors Yasushi Kawase, Kei Kimura, Kazuhisa Makino, Hanna Sumita

Publication date 25 November 2020

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

zbMATH Keywords

NP-hardnessmatroidsPTASpartitioning problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Nonnumerical algorithms (68W05) Approximation algorithms (68W25) Combinatorial aspects of matroids and geometric lattices (05B35)

Recommendations

• Optimal matroid partitioning problems
• Min-Max partitioning problem with matroid constraint
• Constrained partitioning problems
• Approximation algorithms for \(k\)-partitioning problems with partition matroid constraint
• On matroids with multiple objectives

Cites work

• scientific article; zbMATH DE number 6474898 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• 3-partitioning problems for maximizing the minimum load
• A tight bound for 3-partitioning
• A weighted matroid intersection algorithm
• Analytical approach to parallel repetition
• Approximation algorithms for \(k\)-partitioning problems with partition matroid constraint
• Approximation algorithms for scheduling unrelated parallel machines
• Bounds for the cardinality constrained \(P \|C_{max}\) problem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Combinatorial optimization. Theory and algorithms.
• Constrained partitioning problems
• Lower bounds and modified LPT algorithm for \(k\)-partitioning problems with partition matroid constraint
• Matroid matching and some applications
• Matroid matching: the power of local search
• Minimum partition of a matroid into independent subsets
• On the configuration-LP for scheduling on unrelated machines
• On uniform \(k\)-partition problems
• The \(k\)-partitioning problem
• The dense \(k\)-subgraph problem
• Transversals and matroid partition
• \(\kappa\)-partitioning problems for maximizing the minimum load
• \(k\)-partitioning problems with partition matroid constraint

Cited in

(6)

• Multi-objective matroid optimization with ordinal weights
• The complexity of the matroid-greedoid partition problem
• Matroid partition
• Optimal matroid partitioning problems
• Min-Max partitioning problem with matroid constraint
• Optimal Set Partitioning

This page was built for publication: Optimal matroid partitioning problems

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