Cliques and clustering: A combinatorial approach

DOI10.1016/S0167-6377(98)00006-6zbMath0911.90337MaRDI QIDQ1267180

Michael A. Trick, Anuj Mehrotra

Publication date: 6 October 1998

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

Full work available at URL: https://doi.org/10.1016/s0167-6377(98)00006-6

zbMATH Keywords

column generation; constrained clustering; maximum weight clique; branch-and-price method

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C09: Boolean programming

Related Items

A Branch-and-Price Framework for Decomposing Graphs into Relaxed Cliques, Clique Partitioning for Clustering: A Comparison withK-Means and Latent Class Analysis, Subnetwork constraints for tighter upper bounds and exact solution of the clique partitioning problem, Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations, Fixed set search applied to the clique partitioning problem, Efficient enumeration of the optimal solutions to the correlation clustering problem, A branch-and-bound algorithm for the acyclic partitioning problem, Large-scale pickup and delivery work area design, Orbitopal fixing, The robust binomial approach to chance-constrained optimization problems with application to stochastic partitioning of large process networks, A reactive GRASP with path relinking for capacitated clustering, Dual variable based fathoming in dynamic programs for column generation, Solving group technology problems via clique partitioning, Amalgamation of partitions from multiple segmentation bases: a comparison of non-model-based and model-based methods, Clustering qualitative data based on binary equivalence relations: neighborhood search heuristics for the clique partitioning problem, Evaluating balancing on social networks through the efficient solution of correlation clustering problems, The sport teams grouping problem, Reformulated acyclic partitioning for rail-rail containers transshipment, A novel mixed integer linear programming model for clustering relational networks, A branch-and-price-and-cut method for computing an optimal bramble, Capacitated clustering problem in computational biology: combinatorial and statistical approach for sibling reconstruction, A column generation approach to the coalition formation problem in multi-agent systems, A branch-and-price procedure for clustering data that are graph connected, Political districting to minimize cut edges, Multi-attribute community detection in international trade network, An overview of graph covering and partitioning, Unmanned aerial vehicle set covering problem considering fixed-radius coverage constraint, Lagrangian relaxation and pegging test for the clique partitioning problem, Solving the maximum edge-weight clique problem in sparse graphs with compact formulations, Exact algorithms for the minimum \(s\)-club partitioning problem, New bounds and constraint propagation techniques for the clique partitioning problem, Branch-and-price-and-cut on the clique partitioning problem with minimum clique size requirement, Clustering of microarray data via clique partitioning, Classification of Dantzig-Wolfe reformulations for binary mixed integer programming problems, Solving Graph Partitioning Problems Arising in Tagless Cache Management, A Lagrangian Bound on the Clique Number and an Exact Algorithm for the Maximum Edge Weight Clique Problem

Uses Software

• MINTO

Cites Work

• Facets of the clique partitioning polytope
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• A cutting plane algorithm for a clustering problem
• The node capacitated graph partitioning problem: A computational study
• A fast algorithm for the maximum weight clique problem
• Min-cut clustering
• Solving binary cutting stock problems by column generation and branch- and-bound
• MINTO, a Mixed INTeger Optimizer
• Formulations and valid inequalities of the node capacitated graph partitioning problem
• The partition problem
• Branch-and-Price: Column Generation for Solving Huge Integer Programs
• Minimum Weighted Coloring of Triangulated Graphs, with Application to Maximum Weight Vertex Packing and Clique Finding in Arbitrary Graphs
• On the Maximum Weight Clique Problem
• On the multiway cut polyhedron
• Minimum cuts and related problems
• The Graph Partitioning Polytope on Series-Parallel and 4-Wheel Free Graphs
• A Column Generation Approach for Graph Coloring
• On the cut polytope
• A Selection Problem of Shared Fixed Costs and Network Flows