Index coding has received considerable attention recently motivated in part by applications such as fast video-on-demand and efficient communication in wireless networks and in part by its connection to network coding. Optimal encoding schemes and efficient heuristics were studied in various settings, while also leading to new results for network coding such as improved gaps between linear and non-linear capacity as well as hardness of approximation. The problem of broadcasting with side information, a generalization of the index coding problem, begins with a sender and sets of users and messages. Each user possesses a subset of the messages and desires an additional message from the set. The sender wishes to broadcast a message so that on receipt of the broadcast each user can compute her desired message. The fundamental parameter of interest is the broadcast rate,$\beta $, the average communication cost for sufficiently long broadcasts. Though there have been many new nontrivial bounds on$\beta $by Bar-Yossef(2006), Lubetzky and Stav (2007), Alon(2008), and Blasiak(2011) there was no known polynomial-time algorithm for approximating$\beta $within a nontrivial factor, and the exact value of$\beta $remained unknown for all nontrivial instances. Using the information theoretic linear program introduced in Blasiak(2011), we give a polynomial-time algorithm for recognizing instances with$\beta = 2$and pinpoint$\beta $precisely for various classes of graphs (e.g., various Cayley graphs of cyclic groups). Further, extending ideas from Ramsey theory, we give a polynomial-time algorithm with a nontrivial approximation ratio for computing$\beta $. Finally, we provide insight into the quality of previous bounds by giving constructions showing separations between$\beta $and the respective bounds. In particular, we construct graphs where$\beta $is uniformly bounded while its upper bound derived from the naïve encoding scheme is polynomially worse.

We introduce a technique for establishing and amplifying gaps between parameters of network coding and index coding problems. The technique uses linear programs to establish separations between combinatorial and coding-theoretic parameters and applies hyper graph lexicographic products to amplify these separations. This entails combining the dual solutions of the lexicographic multiplicands and proving that this is a valid dual solution of the product. Our result is general enough to apply to a large family of linear programs. This blend of linear programs and lexicographic products gives a recipe for constructing hard instances in which the gap between combinatorial or coding-theoretic parameters is polynomially large. We find polynomial gaps in cases in which the largest previously known gaps were only small constant factors or entirely unknown. Most notably, we show a polynomial separation between linear and non-linear network coding rates. This involves exploiting a connection between matroids and index coding to establish a previously unknown separation between linear and non-linear index coding rates. We also construct index coding problems with a polynomial gap between the broadcast rate and the trivial lower bound for which no gap was previously known.

The minimum latency problem (MLP) is a well-studied variant of the traveling salesman problem (TSP). In the MLP, the server's goal is to minimize the average latency that the clients experience prior to being served, rather than the total latency experienced by the server (as in the TSP). The MLP sometimes goes by other names, such as the traveling repairman problem, or the deliveryman problem. Unlike most combinatorial optimization problems, the MLP is NP-hard even on trees (Sitters, 2001). Our main result is an improved approximation algorithm for the MLP on trees, upon which we build improved approximation algorithms for a much wider class of graphs. The MLP on trees is interesting for several reasons. First, many of the aspects that make the problem difficult on general graphs are already present in the tree case. Second, all existing approximation algorithms for general graphs are built on approximation algorithms for the tree case. Third, there has been no improvement for the tree case since the 3.59-approximation of Goemans and Kleinberg, first introduced 14 years ago in 1996. Fourth, in the intervening period, the best ratio for general metrics has been improved to match the 3.59 for trees (Chaudhuri et al., 2003). In this paper, we improve the approximation ratio for trees to 3.03. In fact, our 3.03-approximation algorithm works for any class of graphs in which the related prize-collecting stroll (PCS) problem is solvable in polynomial time, such as graphs of constant treewidth. More generally, for any class of graphs that admit a Lagrangian-preserving β-approximation algorithm, we can use this algorithm as a black box to achieve a 3.03β-approximation for the MLP. Sadly, this does not immediately improve the ratio of 3.59 for general graphs, because the current best value of β for that case is 2. One interesting piece of our analysis is the solution of an infinite-dimensional linear program, used to analyze a finite-dimensional factor-revealing linear program (FRLP). We believe that our methods may hold promise for easing the analysis of other FRLPs encountered in the literature.