Unveiling Variables in Systems of Linear Equations

Behzad Golshan, Evimaria Terzi

Abstract

Motivated by emerging applications including vehicular traffic networks and crowdsourcing systems, we introduce the Unveil problem defined as follows: given a system of linear equations with less equations than unknowns (i.e., an underdetermined system), identify a set of k variables to query their values so that the number of variables that can be uniquely deduced in the new system is maximized. In this paper, we study the complexity of the Unveil problem and several of its variants and we obtain the following results. In Unveil, when the variables of the linear system take real values, then the problem is NP-hard to solve or even approximate. These inapproximability results carry over to the case where the queries may involve linear combinations of variables. When the variables in the linear equations are binary, then the corresponding binary version of the UNVEIL problem becomes coNP-hard to solve or even approximate. In order to explore the practical significance of our formulation we also develop a set of heuristics for the basic Unveil problem and demonstrate that choosing the queried variables using heuristic algorithms is much more effective than random querying.
BibTeX
@inproceedings{golshan2014unveiling,
  author = {Behzad Golshan and Evimaria Terzi},
  title = {{Unveiling Variables in Systems of Linear Equations}},
  booktitle = {SDM},
  year = {2014},
  doi = {10.1137/1.9781611973440.17},
}

Loading related content...

Figure