Index coding via linear programming

Anna Blasiak, Robert Kleinberg, Eyal Lubetzky
http://arxiv.org/abs/1004.1379

長くて読む気がなかなか湧かないけど．符号の問題．送り手はn個のメッセージx1からxnまでを持っていて，n人いる受け手はそれぞれxiを受け取りたい．そのとき，受け手は自分が受け取りたいもの以外のメッセージを既にいくつか知ってる，という状況を考える．そのような付加的な情報を使うと符号語長が短くて済むかもしれない，ということなのだそうだ．それがindex codingという話のようで，線形計画法を使って符号語長に対するよいboundを出そうという流れ．ちゃんと読んでないけども，Shannon容量と趣きが似ているかもしれないので，組合せ最適化をやってる人は要注目かもしれない．