Pith Number

pith:5GV5C4ML

pith:2026:5GV5C4MLLEQGGTMFNDCJRXWOS6

not attested not anchored not stored refs resolved

Tighter relaxations for MAP-MRF optimization via Singleton Arc Consistency

Asaf Lev-Ran, Pavel Arkhipov, Vladimir Kolmogorov

Running Singleton Arc Consistency on a derived CSP identifies clusters that tighten LP relaxations for MAP-MRF inference more effectively than frustrated cycle search

arxiv:2605.13392 v1 · 2026-05-13 · cs.DS

Open paper page JSON Open Graph Bundle Merged state Verified badge What is a Pith Number?

Add to your LaTeX paper

\usepackage{pith}
\pithnumber{5GV5C4MLLEQGGTMFNDCJRXWOS6}

Prints a linked badge after your title and injects PDF metadata. Compiles on arXiv. Learn more · Embed verified badge

Record completeness

1 Bitcoin timestamp

2 Internet Archive

3 Author claim open · sign in to claim

4 Citations open

5 Replications open

✓ Portable graph bundle live · download bundle · merged state

The bundle contains the canonical record plus signed events. A mirror can host it anywhere and recompute the same current state with the deterministic merge algorithm.

Claims

C1strongest claim

Experimental results indicate that the new tightening technique outperforms the previous approach by Sontag et al. UAI 2012 that searches for frustrated cycles.

C2weakest assumption

That the clusters discovered by Singleton Arc Consistency are sufficiently numerous and cheap to enumerate to produce a practically useful tightening of the LP relaxation on real-world instances.

C3one line summary

Singleton Arc Consistency yields a new cluster-finding procedure that tightens MAP-MRF LP relaxations more effectively than frustrated-cycle search.

References

38 extracted · 38 resolved · 0 Pith anchors

[1] Prestwich, Thomas Schiex, and Seydou Traor \'e 2014

[2] A new algorithm for singleton arc consistency 2004

[3] Markov Random Fields for Vision and Image Processing 2011

[4] D. Batra, S. Nowozin, and P. Kohli. Tighter relaxations for MAP-MRF inference: A local primal-dual gap based separation algorithm. In International Conference on Artificial Intelligence and Statistics 2011

[5] Christian Bessi \`e re, Jean-Charles R \'e gin, Roland H. C. Yap, and Yuanlin Zhang. An optimal coarse-grained arc consistency algorithm. Artificial Intelligence , 165(2):165--185, 2005 2005

Receipt and verification

First computed	2026-05-18T02:44:47.698603Z
Builder	pith-number-builder-2026-05-17-v1
Signature	Pith Ed25519 (`pith-v1-2026-05`) · public key
Schema	pith-number/v1.0

Canonical hash

e9abd1718b5920634d8568c498dece97a283f2c10699e49b99915bfa4db576f8

Aliases

arxiv: 2605.13392 · arxiv_version: 2605.13392v1 · doi: 10.48550/arxiv.2605.13392 · pith_short_12: 5GV5C4MLLEQG · pith_short_16: 5GV5C4MLLEQGGTMF · pith_short_8: 5GV5C4ML

Agent API

Resolver JSON Graph JSON Events JSON Schema Signing key

Verify this Pith Number yourself

curl -sH 'Accept: application/ld+json' https://pith.science/pith/5GV5C4MLLEQGGTMFNDCJRXWOS6 \
  | jq -c '.canonical_record' \
  | python3 -c "import sys,json,hashlib; b=json.dumps(json.loads(sys.stdin.read()), sort_keys=True, separators=(',',':'), ensure_ascii=False).encode(); print(hashlib.sha256(b).hexdigest())"
# expect: e9abd1718b5920634d8568c498dece97a283f2c10699e49b99915bfa4db576f8

Canonical record JSON

{
  "metadata": {
    "abstract_canon_sha256": "986c3c697888fdf18a66bff564abc1af5674daeb6b62f6612de978b9dc1c1b23",
    "cross_cats_sorted": [],
    "license": "http://creativecommons.org/licenses/by/4.0/",
    "primary_cat": "cs.DS",
    "submitted_at": "2026-05-13T11:50:58Z",
    "title_canon_sha256": "12c8037465f18aadba90c66d823dafddaf4510ef647634ef80c3dba79939052f"
  },
  "schema_version": "1.0",
  "source": {
    "id": "2605.13392",
    "kind": "arxiv",
    "version": 1
  }
}