[6/n]

This is joint work with my advisor @ellen-v.bsky.social .

📍 Don’t miss our poster: Tuesday 11:00–13:30 @ # E-3003

Come chat about NAR, primal-dual reasoning, and how neural networks can think like algorithms 🧠➡️⚙️

[5/n]

We evaluate PDNAR and show:
✅ Strong generalization to larger & OOD instances across three NP-hard tasks (vertex cover, set cover, hitting set)
✅ Utility as algorithmically-informed embeddings on real-world tasks
✅ Performance gains as warm starts in commercial solvers 🚀🧩

[4/n]

But we don’t stop at algorithm replication 🛑

We inject optimal supervision from small problem instances—solved efficiently by IP solvers—to surpass the performance of the algorithm it learns from! 🔥

[3/n]

We align GNNs with primal-dual algorithms via a bipartite representation between primal/dual variables, and theoretically prove it retains performance guarantees 📊📚

[2/n]

PDNAR is a general NAR framework for NP-hard problems, built on the primal-dual approximation paradigm—a powerful tool in both exact and approximate algorithm design 🔧📐

[1/n]

What is NAR?
It trains neural networks to simulate algorithmic executions, imbuing them with structured, algorithmic thinking on real-world data 🧮🤖

But... most NAR work focuses on polynomial-time problems.

❗️Real-world problems like facility location are NP-hard!

Our ✨spotlight paper✨ "Primal-Dual Neural Algorithmic Reasoning" is coming to #ICML2025!

We bring Neural Algorithmic Reasoning (NAR) to the NP-hard frontier 💥

🗓 Poster session: Tuesday 11:00–13:30
📍 East Exhibition Hall A-B, # E-3003
🔗 openreview.net/pdf?id=iBpkz...

🧵