Research map / Learning theory and algorithms / Combinatorial and search optimization
A Message Passing Algorithm for the Minimum Cost Multicut Problem
Check your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add odd-wheel inequalities to cycle-only message passing (ablation) | MP-C · image-seg | LB: 4434.69 -> 4434.71 | No clear effect |
| Add odd-wheel inequalities to cycle-only message passing (ablation) | MP-C · image-seg | time(s): 21.92 -> 41.35 | Hurt |
| Add odd-wheel inequalities to cycle-only message passing (ablation) | MP-C · modularity clustering | LB: -0.53 -> -0.53 | No clear effect |
| Add odd-wheel inequalities to cycle-only message passing (ablation) | MP-C · CREMI-large | LB: -3892753.21 -> -3893090.30 | Hurt |
| Use message-passing multicut optimization instead of MC-ILP | image-seg · image-seg | time(s): 11.89 -> 41.35 | Hurt |
| Use message-passing multicut optimization instead of MC-ILP | modularity clustering · modularity clustering | time(s): 2911.10 -> 0.80 | Helped |
Closest papers by meaning
- Box Facets and Cut Facets of Lifted Multicut Polytopes (ICML 2024 · similarity 0.87)
- A Convex Relaxation for Multi-Graph Matching (CVPR 2019 · similarity 0.85)
- Combinatorial Persistency Criteria for Multicut and Max-Cut (CVPR 2019 · similarity 0.85)
- ROS: A GNN-based Relax-Optimize-and-Sample Framework for Max-$k$-Cut Problems (ICML 2025 · similarity 0.84)
- Faster Global Minimum Cut with Predictions (ICML 2025 · similarity 0.82)
- Learning-Augmented Approximation Algorithms for Maximum Cut and Related Problems (NeurIPS 2024 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.