Probability of unique integer solution to a system of linear equations

Probability of unique integer solution to a system of linear equations,10.1016/j.ejor.2011.04.010,European Journal of Operational Research,O. L. Manga

Probability of unique integer solution to a system of linear equations   (Citations: 4)
BibTex | RIS | RefWorks Download
We consider a system of m linear equations in n variables Ax=d and give necessary and sufficient conditions for the existence of a unique solution to the system that is integer: x∈{−1,1}n. We achieve this by reformulating the problem as a linear program and deriving necessary and sufficient conditions for the integer solution to be the unique primal optimal solution. We show that as long as m is larger than n/2, then the linear programming reformulation succeeds for most instances, but if m is less than n/2, the reformulation fails on most instances. We also demonstrate that these predictions match the empirical performance of the linear programming formulation to very high accuracy.
Journal: European Journal of Operational Research - EJOR , vol. 214, no. 1, pp. 27-30, 2011
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...Related results [7] along those lines show that as long as the number of rows is greater than half the number of columns of A, and all sets of m columns of A are linearly independent with probability 1 and each column of A is symmetrically distributed around the origin, then with probability exceeding 1 ,...

    O. L. Mangasarianet al. Uniqueness of integer solution of linear equations

    • ...Given the eigenvalues of a matrix and additionally a few linear measurements of the matrix, when can we recover the matrix? When does a system of linear equations have a unique integer solution? This question is related to the integrality gap between a class of integer linear programs and their linear-programming relaxations, and has previously been studied in [8], [14]...
    • ...This corresponds to a version of the multiknapsack problem [14]...
    • ...This agrees with results obtained in [8], [14]...

    Venkat Chandrasekaranet al. The Convex algebraic geometry of linear inverse problems

    • ...Also, it is interesting to note that if α → 1 then β → 1. This means that in binary compressed sensing one needs at most m = n measurements no matter how sparse the signal is (more on this phenomenon the interested reader can find in an excellent recent work [20])...

    Mihailo Stojnic. Recovery thresholds for ℓ1 optimization in binary compressed sensing

Sort by: