Turnpike with Uncertain Measurements: Triangle-Equality ILP with a Deterministic Recovery Guarantee
We study Turnpike with uncertain measurements: reconstructing a one-dimensional point set from an unlabeled multiset of pairwise distances under bounded noise and rounding. We give a combinatorial characterization of realizability via a multi-matching that labels interval indices by distinct distance values while satisfying all triangle equalities. This yields an ILP based on the triangle equality whose constraint structure depends only on the two-partition set $\mathcal{P}_y=\{(r,s,t): y_r+y_s=y_t\}$ and a natural LP relaxation with $\{0,1\}$-coefficient constraints. Integral solutions…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2603.18283
curl -X POST /api/v1/records/arxiv/2603.18283/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2603.18283/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'