Randomized Relaxation Methods for the Maximum Feasible Subsystem Problem

摘要: In the Max FS problem, given an infeasible linear system Ax ≥ b, one wishes to find a feasible subsystem containing maximum number of inequalities. This NP-hard problem has interesting applications in variety fields. some challenging telecommunications and computational biology faces very large instances with up millions inequalities thousands variables. We propose tackle large-scale using randomized thermal variants classical relaxation method for solving systems present theoretical analysis particular version such which we derive lower bound on probability that it identifies optimal solution within iterations. bound, is expressed as function condition input data, implies 1 after finitely many also results obtained medium- arising planning digital video broadcasts modelling energy functions driving protein folding. Our experiments indicate these methods perform well practice.