DROPS

Document

DOI: 10.4230/LIPIcs.WABI.2026.20

Turnpike with Uncertain Measurements: Triangle-Equality Integer Programming with a Deterministic Recovery Guarantee

Authors: C. S. Elder, Guillaume Marçais, and Carl Kingsford

Published in: LIPIcs, Volume 390, 26th International Conference on Algorithms for Bioinformatics (WABI 2026)

Abstract

We study the Turnpike problem 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 integer linear program (ILP) based on the triangle equality whose constraint structure depends only on the two-partition set P_y = {(r,s,t): y_r + y_s = y_t, (r ≠ s or μ_r ≥ 2)} and a natural linear-programming (LP) relaxation with {0,1}-coefficient constraints. Integral solutions certify realizability and output an explicit assignment matrix, enabling a modular assignment-first, regression-second pipeline for downstream coordinate estimation. Under bounded noise followed by rounding, we prove deterministic separation conditions under which distinct rounded values do not collide and 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.

Cite as

C. S. Elder, Guillaume Marçais, and Carl Kingsford. Turnpike with Uncertain Measurements: Triangle-Equality Integer Programming with a Deterministic Recovery Guarantee. In 26th International Conference on Algorithms for Bioinformatics (WABI 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 390, pp. 20:1-20:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{elder_et_al:LIPIcs.WABI.2026.20,
  author =	{Elder, C. S. and Mar\c{c}ais, Guillaume and Kingsford, Carl},
  title =	{{Turnpike with Uncertain Measurements: Triangle-Equality Integer Programming with a Deterministic Recovery Guarantee}},
  booktitle =	{26th International Conference on Algorithms for Bioinformatics (WABI 2026)},
  pages =	{20:1--20:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-446-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{390},
  editor =	{El-Mabrouk, Nadia and Vandin, Fabio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2026.20},
  URN =		{urn:nbn:de:0030-drops-275240},
  doi =		{10.4230/LIPIcs.WABI.2026.20},
  annote =	{Keywords: Turnpike problem, partial digest, integer linear programming, LP relaxation, unlabeled distances, partitions, bounded noise}
}

Search Results

Documents authored by Elder, C. S.

Turnpike with Uncertain Measurements: Triangle-Equality Integer Programming with a Deterministic Recovery Guarantee

Abstract

Cite as

Thanks for your feedback!

Could not send message