Local tests imply scaled dual feasibility
ProvedDualSepClusterLP.separatorLocalFeasibilityapproximation-algorithmscorrelation-clusteringseparation-oracles
If the singleton and near-clique candidates satisfy their dual constraints and every two-pivot universe meets the additive lower bound, dividing all prices by one plus the requested accuracy makes every dual constraint feasible. The statement allows arbitrary signed prices.
Preamble
import Definitions.Def_DualSepClusterLP_SeparationChecks import Definitions.Def_DualSepClusterLP_SeparationEncoding
Formal statement
namespace DualSepClusterLP
theorem separatorLocalFeasibility {n : ℕ} (t : ℕ) (G : Graph n) (q : Fin n → ℚ) (h : SepCheck.Checks t G q) :
DualFeasible G (fun i => (q i:ℝ)/(1+1/((t:ℝ)+1))) := by sorry
end DualSepClusterLPSource
David García-Soriano and Antoine Schohn, Approximate Dual Separation for the Cluster LP, Theorem 2.1, the large/small/intermediate cost regimes, and the dense quadratic subroutine. https://arxiv.org/abs/2607.27829. The two-pivot localization is an alternative proof for the application.