TU Berlin

Fakultät Elektrotechnik und InformatikAbstract Koana

Inhalt des Dokuments

zur Navigation

Tomohiro Koana, M.Sc. Computer Science (Informatik)

Lupe

Titel der Masterarbeit

Algorithmic and Structural Aspects of Matrix Completion Problems

Abstract

In dieser Arbeit untersuchen wir kombinatorische Matrixvervollständigungsprobleme basierend auf den Arbeiten in der Literatur. Als Eingabe erhalten wir eine unvollständige Matrix mit n Zeilen und l Spalten, in der Werte für einige Einträge unbekannt sind.

Das Ziel ist es, die fehlenden Einträge so zu vervollständigen, dass die Matrix eine gewünschte Eigenschaft erfüllt. Wir betrachten das Ziel, den Radius (maximale Entfernung zu einem Vektor), den lokalen Radius (maximale Entfernung zu einem Vektor in der Matrix) oder den Durchmesser (maximale paarweise Entfernung) der vollständigen Matrix zu minimieren.

Wir nennen diese Probleme Minimum Radius / Local Radius / Diameter Matrix Completion (MinRMC / MinLRMC / MinDMC). Wir untersuchen die algorithmische Komplexität dieser Matrixvervollständigungsprobleme anhand eines multivariaten Ansatzes.

Zunächst beschäftigen wir uns mit MinRMC und MinLRMC. Das Problem der Vervollständigung der Matrix ist NP-schwer, auch wenn der (lokale) Radius d der gesuchten Matrix zwei beträgt. Für den Fall d = 1 entwickeln wir Polynomialzeitalgorithmen, die eine offene Frage von Hermelin und Rozenberg aus dem Jahr 2015 beantworten.

Obwohl MinRMC auch bei vollständiger Matrix NP-schwer ist, zeigen wir fixed-parameter tractability für den Parameter d + k, wobei die maximale Anzahl fehlender Einträge in einer Zeile k ist. Außerdem zeigen wir, dass MinLRMC fixed-parameter tractable für den Parameter k ist.

Dann studieren wir MinDMC. Wir erhalten eine vollständige Dichotomie zwischen lösbaren und unlösbaren Fällen in Bezug auf d und k für binäre Matrizen. Wir entwickeln Polynomzeitalgorithmen für den Fall d ≤ 3, basierend auf Dezas Theorem aus der Theorie der extremalen Mengenlehre.

Auf der negativen Seite beweisen wir die NP-Schwere für den Fall d ≥ 3.

Für den Parameter k zeigen wir, dass MinDMC für k = 1 polynomzeitlösbar ist und NP-schwer, wenn k ≥ 2.

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe