Recursos de colección

CiteSeerX Scientific Literature Digital Library and Search Engine (4.231.670 recursos)

CiteSeerX is a scientific literature digital library and search engine that focuses primarily on the literature in computer and information science. CiteSeerx aims to improve the dissemination of scientific literature and to provide improvements in functionality, usability, availability, cost, comprehensiveness, efficiency, and timeliness in the access of scientific and scholarly knowledge

Mostrando recursos 1 - 20 de 4.144.429

  1. A combination of flow shop scheduling and the shortest path problem

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

  2. A tabu search algorithm for the minmax regret minimum spanning tree problem with . . .

    Adam Kasperski; Mariusz Makuchowski; Pawel Zieliński

  3. A New Construction Method for Networks from Matroids

    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 FD-relation which...

  4. New approaches to multi-objective optimization

    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 NP-hard 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...

  5. An Equivalence between Network Coding and Index Coding

    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 non-linear 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.

  6. New Approaches to Multi-Objective Optimization

    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 NP-hard 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...

  7. An Equivalence between Network Coding and Index Coding

    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 non-linear 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.

  8. Tools for primal degenerate linear programs: IPS, DCA, and PE

    Jean Bertrand Gauthier; Jacques Desrosiers; Marco E. Lübbecke
    This paper describes three recent tools for dealing with primal degen-eracy 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 corre-spond to nondegenerate basic variables. This leads to a row-reduced 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...

  9. Semidefinite relaxation of . . .

    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...

  10. Structural properties of index coding capacity using fractional graph theory

    Fatemeh Arbabjolfaei; Young-han Kim
    The capacity region of the index coding prob-lem 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 graph-theoretic 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, one-way, or complete.

  11. Approximation Schemes for Multi-Budgeted Independence Systems

    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 NP-hard even with one budget constraint. Still, for most of these problems efficient deterministic and randomized approximation schemes are known. For two or more bud-gets, typically only multi-criteria approximation schemes are available, which return slightly infeasible solutions. Not much is known however for strict budget constraints: filling this gap is the main...

  12. On the Index Coding Problem and its Relation to Network Coding and Matroid Theory

    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 ad-hoc 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...

  13. Index coding and fractional graph theory

    Fatemeh Arbabjolfaei; Young-han Kim

  14. A Heuristic for the Stability Number of a Graph based on Convex Quadratic Programming and Tabu Search

    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 two-phase heuristic for...

  15. A computational approach for determining rate regions and codes using entropic vector bounds

    Congduan Li; John MacLaren Walsh; Steven Weber

  16. Quadratic maximization and semidefinite relaxation

    Shuzhong Zhang

  17. Relation between pairs of representations of signed binary matroids

    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.

  18. Semidefinite programming bounds for spherical codes

    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.

  19. Bounds on Entanglement Assisted Source-channel Coding via the Lovász ϑ Number and its Variants

    Toby Cubitt; David Roberson; Simone Severini; Dan Stahlke; Andreas Winter, et al.
    We study zero-error entanglement assisted source-channel 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...

  20. Matchings in Benjamini–Schramm convergent graph sequences

    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 loga-rithm 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...

Aviso de cookies: Usamos cookies propias y de terceros para mejorar nuestros servicios, para análisis estadístico y para mostrarle publicidad. Si continua navegando consideramos que acepta su uso en los términos establecidos en la Política de cookies.