Clique partitioning with value-monotone submodular cost

DOI10.1016/J.DISOPT.2014.11.001MaRDI QIDQ2339847zbMATH OpenOpenAlexDBLPWikidataFDO

Authors José R. Correa, Nicole Megow

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 cliquescost coloringmax-coloringbatch-scheduling with compatibilities

Mathematics Subject Classification ID

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

Recommendations

• Clique partitioning of interval graphs with submodular costs on the cliques
• The clique-partitioning problem
• A generalized minimum cost k-clustering
• Clustering with Local Restrictions
• Clustering with local restrictions

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 219236 (Why is no real title available?)
• A Characterization of Comparability Graphs and of Interval 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
• A note on two problems in connexion with graphs
• Approximation schemes for covering and packing problems in image processing and VLSI
• Automata, Languages and Programming
• Batch processing with interval graph compatibilities between tasks
• Bounded Max-colorings of Graphs
• Bounded vertex colorings of graphs
• Capacitated max-batching with interval graph compatibilities
• Clique Clustering Yields a PTAS for max-Coloring Interval Graphs
• Clique partitioning of interval graphs with submodular costs on the cliques
• Combinatorial auctions with decreasing marginal utilities
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Minimax relations for the partial q-colorings of a graph
• Minimum entropy coloring
• Minimum entropy combinatorial optimization problems
• Mutual exclusion scheduling
• Mutual exclusion scheduling with interval graphs or related classes. I
• NP-completeness of graph decomposition problems
• On the Max Coloring Problem
• On the probabilistic minimum coloring and minimum \(k\)-coloring
• Probabilistic graph-coloring in bipartite and split graphs
• Restrictions of graph partition problems. I
• Scheduling on a batch machine with job compatibilities
• Scheduling on a batch processing machine with split compatibility graphs
• Source coding and graph entropies
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The Joint Replenishment Problem with General Joint Cost Structures
• The clique-separator graph for chordal graphs
• The facility location problem with general cost functions
• The mutual exclusion scheduling problem for permutation and comparability graphs.
• Time slot scheduling of compatible jobs
• Weighted coloring on planar, bipartite and split graphs: Complexity and approximation
• Weighted coloring: further complexity and approximability results
• Zero-error information theory

Cited in

(2)

• Interval scheduling with economies of scale
• Clique partitioning of interval graphs with submodular costs on the cliques

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

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