Exact Information Prices in a Full-Partition LP: Joint Weight and Tolerance Sensitivity

We determine the exact value of a full-partition linear programming relaxation as two objective weights and two observation tolerances vary over the nonnegative reals. The model has eight vertices, three soft terminals and six local probability laws, each supported on all 4,140 set partitions. The laws share terminal moments and are coupled by three selected pair observations, the third of which has zero tolerance. The value has six parameter regimes. Five rational dual certificates bound every original partition column; explicit partition laws attain the bounds through convex interpolation and weight-cone decompositions. After normalizing the total objective weight, the formula is the upper concave envelope of four priced points. This representation explains the transition lines between regimes. We also give exact examples in which local relay prices, and then a combined cell-triple certificate, miss a positive joint gain. Finally, we prove additivity for any finite number of modules with disjoint private vertices, three common terminals and no cross-module private-pair observations. The results describe the specified relaxation and certificate libraries; they provide neither a five-parameter formula nor exactness for arbitrary overlapping networks.

Authors

Institutions

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-16
DOI
https://doi.org/10.5281/zenodo.24271839
Primary Topic
Complexity and Algorithms in Graphs
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Exact Information Prices in a Full-Partition LP: Joint Weight and Tolerance Sensitivity

Shuai Zhang, Shuhao Zhang
2 links
Zenodo (CERN European Organization for Nuclear Research)
Complexity and Algorithms in Graphs
preprint

Exact Information Prices in a Full-Partition LP: Joint Weight and Tolerance Sensitivity

Shuai Zhang, Shuhao Zhang
preprint en

Abstract

We determine the exact value of a full-partition linear programming relaxation as two objective weights and two observation tolerances vary over the nonnegative reals. The model has eight vertices, three soft terminals and six local probability laws, each supported on all 4,140 set partitions. The laws share terminal moments and are coupled by three selected pair observations, the third of which has zero tolerance. The value has six parameter regimes. Five rational dual certificates bound every original partition column; explicit partition laws attain the bounds through convex interpolation and weight-cone decompositions. After normalizing the total objective weight, the formula is the upper concave envelope of four priced points. This representation explains the transition lines between regimes. We also give exact examples in which local relay prices, and then a combined cell-triple certificate, miss a positive joint gain. Finally, we prove additivity for any finite number of modules with disjoint private vertices, three common terminals and no cross-module private-pair observations. The results describe the specified relaxation and certificate libraries; they provide neither a five-parameter formula nor exactness for arbitrary overlapping networks.

Zenodo (CERN European Organization for Nuclear Research)
Beijing Technology and Business University (CN), Beijing Forestry University (CN)
Complexity and Algorithms in Graphs
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon