
Kameng Nip; Zhenbo Wang; Fabrice Talla Nobibon; Roel Leus

Adam Kasperski; Mariusz Makuchowski; Pawel Zieliński

Salim El Rouayheb; Alex Sprintson; Costas Georghiades
We study the problem of information flow in communication networks with noiseless links in which the dependency relations among the data flowing on the different network edges satisfy matroidal constraints. We present a construction that maps any given matroid to a network that admits vector linear network codes over a certain field if and only if the matroid has a multilinear representation over the same field. This new construction strengthens previous results in the literature and, thus, establishes a deeper connection between network coding and matroid theory. We also explore another, more general, mathematical construct referred to as FDrelation which...

Fabrizio Grandoni; R. Ravi; Mohit Singh; Rico Zenklusen
A natural way to deal with multiple, partially conflicting objectives is turning all the objectives but one into budget constraints. Many classical optimization problems, such as maximum spanning tree and forest, shortest path, maximum weight (perfect) matching, maximum weight independent set (basis) in a matroid or in the intersection of two matroids, become NPhard even with one budget constraint. Still, for most of these problems efficient deterministic and randomized approximation schemes are known. Not much is known however about the case of two or more budgets: filling this gap, at least partially, is the main goal of this paper. In...

M. Effros; S. El Rouayheb; M. Langberg
We show that the network coding and index coding problems are equivalent. This equivalence holds in the general setting which includes linear and nonlinear codes. Specifically, we present an efficient reduction that maps a network coding instance to an index coding one while preserving feasibility. Previous connections were restricted to the linear case.

Fabrizio Grandoni, et al.
A natural way to deal with multiple, partially conflicting objectives is turning all the objectives but one into budget constraints. Many classical optimization problems, such as maximum spanning tree and forest, shortest path, maximum weight (perfect) matching, maximum weight independent set (basis) in a matroid or in the intersection of two matroids, become NPhard even with one budget constraint. Still, for most of these problems efficient deterministic and randomized approximation schemes are known. Not much is known however about the case of two or more budgets: filling this gap, at least partially, is the main goal of this paper. In...

Michelle Effros; Salim El Rouayheb; Michael Langberg
We show that the network coding and index coding problems are equivalent. This equivalence holds in the general setting which includes linear and nonlinear codes. Specifically, we present an efficient reduction that maps a network coding instance to an index coding instance while preserving feasibility. Previous connections were restricted to the linear case.

Jean Bertrand Gauthier; Jacques Desrosiers; Marco E. Lübbecke
This paper describes three recent tools for dealing with primal degeneracy in linear programming. The first one is the improved primal simplex (IPS) algorithm which turns degeneracy into a possible advantage. The constraints of the original problem are dynamically partitioned based on the numerical values of the current basic variables. The idea is to work only with those constraints that correspond to nondegenerate basic variables. This leads to a rowreduced problem which decreases the size of the current working basis. The main feature of IPS is that it provides a nondegenerate pivot at every iteration of the solution process until...

Luo, et al.
In recent years, the semidefinite relaxation (SDR) technique has been at the center of some of very exciting developments in the area of signal processing and communications, and it has shown great significance and relevance on a variety of applications. Roughly speaking, SDR is a powerful, computationally efficient approximation technique for a host of very difficult optimization problems. In particular, it can be applied to many nonconvex quadratically constrained quadratic programs (QCQPs) in an almost mechanical fashion, including the following problem: min x[Rn xTCx s.t. xTFi x $ gi, i5 1,c, p, xTHi x5 li, i5 1,c, q, (1) where...

Fatemeh Arbabjolfaei; Younghan Kim
The capacity region of the index coding problem is characterized through the notion of confusion graph and its fractional chromatic number. Based on this multiletter characterization, several structural properties of the capacity region are established, some of which are already noted by Tahmasbi, Shahrasbi, and Gohari, but proved here with simple and more direct graphtheoretic arguments. In particular, the capacity region of a given index coding problem is shown to be simple functionals of the capacity regions of smaller subproblems when the interaction between the subproblems is none, oneway, or complete.

Fabrizio Grandoni; Rico Zenklusen
A natural way to deal with multiple, partially conflicting objectives is turning all the objectives but one into budget constraints. Some classical optimization problems, such as spanning tree and forest, shortest path, (perfect) matching, independent set (basis) in a matroid or in the intersection of two matroids, become NPhard even with one budget constraint. Still, for most of these problems efficient deterministic and randomized approximation schemes are known. For two or more budgets, typically only multicriteria approximation schemes are available, which return slightly infeasible solutions. Not much is known however for strict budget constraints: filling this gap is the main...

Salim El Rouayheb; Alex Sprintson; Costas Georghiades
The index coding problem has recently attracted a significant attention from the research community due to its theoretical significance and applications in wireless adhoc networks. An instance of the index coding problem includes a sender that holds a set of information messages X = {x1,..., xk} and a set of receivers R. Each receiver ρ = (x,H) in R needs to obtain a message x ∈ X and has prior side information consisting of a subset H of X. The sender uses a noiseless communication channel to broadcast encoding of messages in X to all clients. The objective is to...

Fatemeh Arbabjolfaei; Younghan Kim

L. Cavique; C. J. Luz
Recently a characterization of the Lovász theta number based on convex quadratic programming was established. As a consequence of this formulation, we introduce a new upper bound on the stability number of a graph which slightly improves the theta number. Like this number, the new bound can be characterized as the minimum of a function whose values are the optimum values of convex quadratic programs. This paper is mainly oriented to the following question: how can the new bound be used to approximate the maximum stable set for large graphs? With this in mind we present a twophase heuristic for...

Congduan Li; John MacLaren Walsh; Steven Weber

Shuzhong Zhang

Bertrand Guenin; Irene Pivotto; Paul Wollan
We show how pairs of signed graphs with the same even cycles relate to pairs of grafts with the same even cuts. These results are proved in the more general context of signed binary matroids.

Christine Bachoc; Frank Vallentin
This paper develops a new method to obtain upper bounds for spherical codes, based on semidefinite programming. With this method we improve the previous bounds for the kissing number in several dimensions, as well as other classical problems like Tammes’ problem.

Toby Cubitt; David Roberson; Simone Severini; Dan Stahlke; Andreas Winter, et al.
We study zeroerror entanglement assisted sourcechannel coding (communication in the presence of side information). Adapting a technique of Beigi, we show that such coding requires existence of a set of vectors satisfying orthogonality conditions related to suitably defined graphs G and H. Such vectors exist if and only if ϑ(G) ≤ ϑ(H) where ϑ represents the Lovász number. We also obtain similar inequalities for the related Schrijver ϑ − and Szegedy ϑ+ numbers. These inequalities reproduce several known bounds and also lead to new results. We provide a lower bound on the entanglement assisted cost rate. We show that the...

Miklós Abért; Péter Csikvári; Péter E. Frenkel; Gábor Kun
We introduce the matching measure of a finite graph as the uniform distribution on the roots of the matching polynomial of the graph. We analyze the asymptotic behavior of the matching measure for graph sequences with bounded degree. A graph parameter is said to be estimable if it converges along every Benjamini– Schramm convergent sparse graph sequence. We prove that the normalized logarithm of the number of matchings is estimable. We also show that the analogous statement for perfect matchings already fails for d–regular bipartite graphs for any fixed d ≥ 3. The latter result relies on analyzing the probability...