Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2603.18283 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912973696532480 |
|---|---|
| author | Elder, C. S. Marçais, Guillaume Kingsford, Carl |
| author_facet | Elder, C. S. Marçais, Guillaume Kingsford, Carl |
| contents | 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 certify realizability and output an explicit assignment matrix, enabling an assignment-first, regression-second pipeline for downstream coordinate estimation. Under bounded noise followed by rounding, we prove a deterministic separation condition under which $\mathcal{P}_y$ is recovered exactly, so the ILP/LP receives the same combinatorial input as in the noiseless case. Experiments illustrate integrality behavior and degradation outside the provable regime. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_18283 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Turnpike with Uncertain Measurements: Triangle-Equality ILP with a Deterministic Recovery Guarantee Elder, C. S. Marçais, Guillaume Kingsford, Carl Computational Geometry Data Structures and Algorithms Optimization and Control 90C10, 90C05, 05B35, 68R10 G.1.6; F.2.2; I.3.5 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 certify realizability and output an explicit assignment matrix, enabling an assignment-first, regression-second pipeline for downstream coordinate estimation. Under bounded noise followed by rounding, we prove a deterministic separation condition under which $\mathcal{P}_y$ is recovered exactly, so the ILP/LP receives the same combinatorial input as in the noiseless case. Experiments illustrate integrality behavior and degradation outside the provable regime. |
| title | Turnpike with Uncertain Measurements: Triangle-Equality ILP with a Deterministic Recovery Guarantee |
| topic | Computational Geometry Data Structures and Algorithms Optimization and Control 90C10, 90C05, 05B35, 68R10 G.1.6; F.2.2; I.3.5 |
| url | https://arxiv.org/abs/2603.18283 |