Research map / Learning theory and algorithms / Combinatorial and search optimization
Unsupervised Learning for Combinatorial Optimization with Principled Objective Relaxation
Read the paperCheck 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 |
|---|---|---|---|
| Use the entry-wise affine relaxation and deterministic rounding instead of RL | unsupervised learning for edge covering · Feature-based edge covering | cost: 51.29 -> 44.55 | Helped |
| Use the entry-wise affine relaxation and deterministic rounding instead of RL | unsupervised learning for node matching · Node matching | cost: 426.97 -> 418.96 | Helped |
| Use the entry-wise concave proxy rather than GS-Tr+R | resource allocation · DSP usage constraint 40%-70% | average LUT-usage rank: 3.37 -> 2.91 | Helped |
| Use the entry-wise proxy and deterministic rounding rather than GS-Tr+R | AxC assignment · 3 units | relative error: 3.24 -> 3.10 | Helped |
| Use the entry-wise proxy and deterministic rounding rather than GS-Tr+R | AxC assignment · 5 units | relative error: 5.86 -> 5.13 | Helped |
| Use the entry-wise proxy and deterministic rounding rather than GS-Tr+R | AxC assignment · 8 units | relative error: 10.62 -> 10.04 | Helped |
| Replace the entry-wise affine proxy with the entry-wise concave proxy (ablation) | edge covering · Feature-based edge covering | cost: 44.55 -> 49.59 | Hurt |
| Replace the entry-wise affine proxy with the entry-wise concave proxy (ablation) | node matching · Node matching | cost: 418.96 -> 422.47 | Hurt |
| Use AFF instead of CON (ablation) | AxC assignment · 3, 5, and 8 units | relative error: 3.18 -> 3.10; 5.13 -> 5.38; 10.17 -> 10.04 | Mixed |
| Use the principled affine relaxation instead of the trigonometric Badloss relaxation | max clique · Twitter | approximation rate: 0.768 ± 0.203 -> 0.926 ± 0.113 | Helped |
| Use the principled affine relaxation instead of the trigonometric Badloss relaxation | max clique · RBtest | approximation rate: 0.702 ± 0.102 -> 0.787 ± 0.065 | Helped |
| Apply deterministic rounding after the relaxed optimization | entry-wise affine and concave proxies · Edge covering, node matching, resource allocation, and AxC circuit design | relaxed loss: See Table: l_r -> l_r' | Helped |
Closest papers by meaning
- Tackling Prevalent Conditions in Unsupervised Combinatorial Optimization: Cardinality, Minimum, Covering, and More (ICML 2024 · similarity 0.90)
- Controlling Continuous Relaxation for Combinatorial Optimization (NeurIPS 2024 · similarity 0.90)
- Towards General Algorithm Discovery for Combinatorial Optimization: Learning Symbolic Branching Policy from Bipartite Graph (ICML 2024 · similarity 0.88)
- Geometric Algorithms for Neural Combinatorial Optimization with Constraints (NeurIPS 2025 · similarity 0.88)
- COMBHelper: A Neural Approach to Reduce Search Space for Graph Combinatorial Problems (AAAI 2024 · similarity 0.88)
- Differentiable Quadratic Optimization For the Maximum Independent Set Problem (ICML 2025 · similarity 0.88)
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.