Clique partitioning with value-monotone submodular cost

DOI10.1016/j.disopt.2014.11.001zbMath1308.90187OpenAlexW2027077687WikidataQ57399730 ScholiaQ57399730MaRDI QIDQ2339847

Nicole Megow, José R. Correa

Publication date: 9 April 2015

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2014.11.001

zbMATH Keywords

submodular functionscardinality constraintpartition into cliquesmax-coloringcost coloringbatch-scheduling with compatibilities

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic scheduling theory in operations research (90B35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

Interval scheduling with economies of scale

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• Restrictions of graph partition problems. I
• Bounded vertex colorings of graphs
• Minimum entropy combinatorial optimization problems
• Probabilistic graph-coloring in bipartite and split graphs
• A min-max relation for the partial q-colourings of a graph. II: Box perfection
• A note on the decomposition of graphs into isomorphic matchings
• Time slot scheduling of compatible jobs
• Mutual exclusion scheduling with interval graphs or related classes. I
• Minimum entropy coloring
• The clique-separator graph for chordal graphs
• Weighted coloring on planar, bipartite and split graphs: Complexity and approximation
• Weighted coloring: further complexity and approximability results
• NP-completeness of graph decomposition problems
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Mutual exclusion scheduling
• The mutual exclusion scheduling problem for permutation and comparability graphs.
• Minimax relations for the partial q-colorings of a graph
• Batch processing with interval graph compatibilities between tasks
• On the probabilistic minimum coloring and minimum \(k\)-coloring
• Combinatorial auctions with decreasing marginal utilities
• Scheduling on a batch processing machine with split compatibility graphs
• Clique partitioning of interval graphs with submodular costs on the cliques
• Clique Clustering Yields a PTAS for max-Coloring Interval Graphs
• Bounded Max-colorings of Graphs
• Capacitated max -Batching with Interval Graph Compatibilities
• Approximation schemes for covering and packing problems in image processing and VLSI
• The Joint Replenishment Problem with General Joint Cost Structures
• The facility location problem with general cost functions
• Zero-error information theory
• Source coding and graph entropies
• On the Max Coloring Problem
• Automata, Languages and Programming
• A Characterization of Comparability Graphs and of Interval Graphs

This page was built for publication: Clique partitioning with value-monotone submodular cost