Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
Fast Deterministic Algorithms for Matrix Completion Problems
verfasst von : Tasuku Soma
Erschienen in: Integer Programming and Combinatorial Optimization
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Ivanoys, Karpinski and Saxena (2010) have developed a deterministic polynomial time algorithm for finding scalars
x
1
, …,
x
n
that maximize the rank of the matrix
B
0
+
x
1
B
1
+ … +
x
n
B
n
for given matrices
B
0
,
B
1
, …,
B
n
, where
B
1
, …,
B
n
are of rank one. Their algorithm runs in
O
(
m
4.37
n
) time, where
m
is the larger of the row size and the column size of the input matrices.
In this paper, we present a new deterministic algorithm that runs in
O
((
m
+
n
)
2.77
) time, which is faster than the previous one unless
n
is much larger than
m
. Our algorithm makes use of an efficient completion method for mixed matrices by Harvey, Karger and Murota (2005). As an application of our completion algorithm, we devise a deterministic algorithm for the multicast problem with linearly correlated sources.
We also consider a skew-symmetric version: maximize the rank of the matrix
B
0
+
x
1
B
1
+ … +
x
n
B
n
for given skew-symmetric matrices
B
0
,
B
1
, …,
B
n
, where
B
1
, …,
B
n
are of rank two. We design the first deterministic polynomial time algorithm for this problem based on the concept of mixed skew-symmetric matrices and the linear delta-covering algorithm of Geelen, Iwata and Murota (2003).