Name
Abstract | ||
|---|---|---|
Abstract Given a matrix whose entries are a mixture of numeric values and symbolic variables, the matrix completion problem is to assign values to the variables so as to maximize the resulting matrix rank. This problem has deep connections to computational complexity and numerous important algorithmic applications. Determining the complexity of this problem is a fundamental open question in computational complexity. Under different settings of parameters, the problem is variously in P, in RP, or NP-hard. We shed new light on this landscape by demonstrating a new region of NP-hard scenarios. As a special case, we obtain the rst known hardness result for matrices in which each variable appears only twice. Another particular scenario that we consider is the simultaneous matrix completion problem, where one must simultaneously maximize the rank for several matrices that share variables. This problem has important applications in the eld of network coding. Recent work has given a simple, greedy, deterministic algorithm for this problem, assuming that the algorithm works over a sucien tly large eld. We show an exact threshold for the eld,size required to nd,a simultaneous completion ecien tly. This result implies that, surprisingly, the simple greedy algorithm is optimal: nding a simultaneous completion over any smaller eld is NPhard. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1145/1109557.1109679 | Symposium on Discrete Algorithms |
Keywords | Field | DocType |
large field,simultaneous matrix completion problem,simultaneous completion,np-hard scenario,smaller field,algorithm work,matrix rank,field size,matrix completion problem,computational complexity,vertex,polyhedron,difference set,facet,face,linear inequalities,greedy algorithm,network coding,polytope,cycle,graph | Rank (linear algebra),Computer science,Matrix (mathematics),Deterministic algorithm,Special case,Discrete mathematics,Combinatorics,Mathematical optimization,Matrix completion,Algorithm,Greedy algorithm,Linear inequality,Computational complexity theory | Conference |
ISBN | Citations | PageRank |
0-89871-605-5 | 22 | 1.67 |
References | Authors | |
16 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nicholas J. A. Harvey | 1 | 909 | 57.85 |
| David R. Karger | 2 | 19367 | 2233.64 |
| Sergey Yekhanin | 3 | 983 | 52.33 |