Deterministic network coding by matrix completion

Nicholas J. A. Harvey, David R. Karger, Kazuo MurotaSODA 2005 · OpenReview

Abstract

We present a new deterministic algorithm to construct network codes for multicast problems, a particular class of network information ow problems. Our algorithm easily generalizes to several variants of multicast problems. Our approach is based on a new algorithm for maximum-rank completion of mixed matrices---taking a matrix whose entries are a mixture of numeric values and symbolic variables, and assigning values to the variables so as to maximize the resulting matrix rank. Our algorithm is faster than existing deterministic algorithms and can operate over a smaller field.
BibTeX
@inproceedings{harvey2005deterministic,
  author = {Nicholas J. A. Harvey and David R. Karger and Kazuo Murota},
  title = {{Deterministic network coding by matrix completion}},
  booktitle = {SODA},
  year = {2005},
  url = {https://openreview.net/forum?id=hHU3HVSNHOy},
}

Loading related content...

Figure