The maximum saving partition problem

DOI10.1016/j.orl.2004.07.007zbMath1274.90312OpenAlexW2093134385MaRDI QIDQ1779697

Jérôme Monnot, Refael Hassin

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)

Related Items (7)

Saving Colors and Max Coloring: Some Fixed-Parameter Tractability Results ⋮ A survey on the structure of approximation classes ⋮ A better differential approximation ratio for symmetric TSP ⋮ Saving colors and max coloring: some fixed-parameter tractability results ⋮ On the differential approximation of MIN SET COVER ⋮ New differential approximation algorithm for \(k\)-customer vehicle routing problem ⋮ Weighted coloring on planar, bipartite and split graphs: Complexity and approximation

Cites Work

• Unnamed Item
• Unnamed Item
• Approximation results for the minimum graph coloring problem
• Chromatic scheduling and frequency assignment
• Maximizing the number of unused colors in the vertex coloring problem
• Scheduling with incompatible jobs
• On chromatic sums and distributed resource allocation
• A hypocoloring model for batch scheduling
• Three-quarter approximation for the number of unused colors in graph coloring
• Bridging gap between standard and differential polynomial approximation: The case of bin-packing
• z-Approximations
• Graph colorings with local constraints -- a survey
• Approximation Results for the Optimum Cost Chromatic Partition Problem

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