Parameterized Algorithms for the Matrix Completion Problem
Authors: Robert Ganian, Iyad Kanj, Sebastian Ordyniak, Stefan Szeider
ICML 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the parameterized complexity of the two aforementioned problems with respect to several parameters of interest, including the minimum number of matrix rows, columns, and rows plus columns needed to cover all missing entries. We obtain new algorithmic results showing that, for the bounded domain case, both problems are fixed-parameter tractable with respect to all aforementioned parameters. We complement these results with a lower-bound result for the unbounded domain case that rules out fixed-parameter tractability w.r.t. some of the parameters under consideration. In this paper, we study the two aforementioned problems through the lens of parameterized complexity (Downey & Fellows, 2013). In this paradigm, one measures the complexity of problems not only in terms of their input size n but also by a certain parameter k N, and seeks among other things fixed-parameter algorithms, i.e., algorithms that run in time f(k) n O(1) for some function f. |
| Researcher Affiliation | Academia | 1 Algorithms and Complexity Group, TU Wien, Vienna, Austria 2 School of Computing, De Paul University, Chicago, USA 3 Algorithms Group, University of Sheffield, Sheffield, UK. |
| Pseudocode | No | The paper describes algorithms in narrative form within the proofs of theorems but does not include structured pseudocode or algorithm blocks (e.g., |
| Open Source Code | No | The paper does not provide any concrete access to source code for the methodology described, such as a repository link or an explicit code release statement. |
| Open Datasets | No | The paper is theoretical and does not involve experimental evaluation on datasets. Therefore, it does not provide information about publicly available or open datasets. |
| Dataset Splits | No | The paper is theoretical and does not involve experimental evaluation with dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not describe experiments, so no specific hardware details are provided. |
| Software Dependencies | No | The paper is theoretical and does not describe software implementation or experimental setup, thus no specific software dependencies with version numbers are mentioned. |
| Experiment Setup | No | The paper is theoretical and does not include details about an experimental setup, hyperparameters, or system-level training settings. |