The maximum saving partition problem

DOI10.1016/J.ORL.2004.07.007MaRDI QIDQ1779697zbMATH OpenOpenAlexFDO

Authors Refael Hassin, Jérôme Monnot

Publication date 1 June 2005

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

Full work available at URL https://doi.org/10.1016/j.orl.2004.07.007

zbMATH Keywords

NP-completeApproximation algorithmsPartitioningColor saving

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27)

Recommendations

• scientific article; zbMATH DE number 1046599
• scientific article; zbMATH DE number 1161371
• The \(k\)-partitioning problem
• Constrained partitioning problems
• scientific article; zbMATH DE number 800169

Cites work

• scientific article; zbMATH DE number 1953087 (Why is no real title available?)
• scientific article; zbMATH DE number 1559541 (Why is no real title available?)
• A hypocoloring model for batch scheduling
• Approximation Results for the Optimum Cost Chromatic Partition Problem
• Approximation results for the minimum graph coloring problem
• Bridging gap between standard and differential polynomial approximation: The case of bin-packing
• Chromatic scheduling and frequency assignment
• Graph colorings with local constraints -- a survey
• Maximizing the number of unused colors in the vertex coloring problem
• On chromatic sums and distributed resource allocation
• Scheduling with incompatible jobs
• Three-quarter approximation for the number of unused colors in graph coloring
• \(z\)-approximations

Cited in

(8)

• New differential approximation algorithm for \(k\)-customer vehicle routing problem
• Weighted coloring on planar, bipartite and split graphs: Complexity and approximation
• On the differential approximation of MIN SET COVER
• Saving colors and max coloring: some fixed-parameter tractability results
• Theoretical Aspects of Computing – ICTAC 2005
• A better differential approximation ratio for symmetric TSP
• Saving colors and max coloring: some fixed-parameter tractability results
• A survey on the structure of approximation classes

This page was built for publication: The maximum saving partition problem

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