Optimal matroid partitioning problems

DOI10.4230/LIPICS.ISAAC.2017.51zbMATH Open1457.68127arXiv1710.00950MaRDI QIDQ5136271FDOQ5136271

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

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

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)

Cites Work

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