Optimal matroid partitioning problems

DOI10.1007/s00453-021-00797-9OpenAlexW3132265628MaRDI QIDQ2032344

Hanna Sumita, Yasushi Kawase, Kazuhisa Makino, Kei Kimura

Publication date: 11 June 2021

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/8271/

zbMATH Keywords

partitioning problemmatroidNP-hardnessPTAS

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Related Items (1)

EPTAS for parallel identical machine scheduling with time restrictions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the configuration-LP for scheduling on unrelated machines
• 3-partitioning problems for maximizing the minimum load
• Approximation algorithms for scheduling unrelated parallel machines
• Lower bounds and modified LPT algorithm for \(k\)-partitioning problems with partition matroid constraint
• \(k\)-partitioning problems with partition matroid constraint
• Matroid matching and some applications
• The \(k\)-partitioning problem
• A tight bound for 3-partitioning
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• \(\kappa\)-partitioning problems for maximizing the minimum load
• Approximation algorithms for \(k\)-partitioning problems with partition matroid constraint
• On uniform \(k\)-partition problems
• Matroid Matching: The Power of Local Search
• A weighted matroid intersection algorithm
• Analytical approach to parallel repetition
• Transversals and matroid partition
• Minimum partition of a matroid into independent subsets
• Constrained partitioning problems
• Combinatorial optimization. Theory and algorithms.
• The dense \(k\)-subgraph problem
• Bounds for the cardinality constrained \(P \|C_{max}\) problem

This page was built for publication: Optimal matroid partitioning problems