5 documentos corresponden a la consulta.
Palabras contadas: polytopes: 10
Marenco, J. - Wagler, A.
Discrete Appl Math 2006;154(13 SPEC ISS):1865-1876
2006
Temas: Bandwidth allocation - Polyhedral combinatorics - Algorithms - Numerical analysis - Optimization - Polynomials - Problem solving - Telecommunication networks - Chromatic scheduling polytopes - Combinatorial structures
Descripción: Fil:Marenco, J. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina.
...ver más Tipo de documento: info:ar-repo/semantics/artículo
Marenco, J. - Wagler, A.
Discrete Optim. 2009;6(1):64-78
2009
Temas: Bandwidth allocation - Facets - Polyhedral combinatorics - Separation - Bandwidth - Combinatorial mathematics - Combinatorial optimization - Isomers - Radio - Scheduling
Descripción: Chromatic scheduling polytopes arise as solution sets of the bandwidth allocation problem in certain radio access networks supplying wireless access to voice/data communication networks to customers with individual communication demands. This bandwidth allocation problem is a special chromatic scheduling problem; both problems are N P-complete and, furthermore, there exist no polynomial-time algorithms with a fixed quality guarantee for them. As algorithms based on cutting planes are shown to be successful for many other combinatorial optimization problems, the goal is to apply such methods to the bandwidth allocation problem. For that, knowledge on the associated polytopes is required. The present paper contributes to this issue, introducing new classes of valid inequalities based on variations and extensions of the covering-clique inequalities presented in [J. Marenco, Chromatic scheduling polytopes coming from the bandwidth allocation problem in point-to-multipoint radio access systems, Ph.D. Thesis, Universidad de Buenos Aires, Argentina, 2005; J. Marenco, A. Wagler, Chromatic scheduling polytopes coming from the bandwidth allocation problem in point-to-multipoint radio access systems, Annals of Operations Research 150-1 (2007) 159-175]. We discuss conditions ensuring that these inequalities define facets of chromatic scheduling polytopes, and we show that the associated separation problems are N P-complete. © 2008 Elsevier B.V. All rights reserved.
...ver más Tipo de documento: info:ar-repo/semantics/artículo
Dickenstein, A. - Di Rocco, S. - Piene, R.
Adv. Math. 2009;222(1):240-254
2009
Descripción: We show that any smooth Q-normal lattice polytope P of dimension n and degree d is a strict Cayley polytope if n ≥ 2 d + 1. This gives a sharp answer, for this class of polytopes, to a question raised by V.V. Batyrev and B. Nill. © 2009 Elsevier Inc. All rights reserved.
...ver más Tipo de documento: info:ar-repo/semantics/artículo
Méndez-Díaz, I. - Zabala, P.
Discrete Appl Math 2010;158(4):349-354
2010
Temas: Branch-and-Cut - Graph multicoloring - Integer programming - Branch-and-cut - Branch-and-cut algorithms - Graph multicoloring - Integer programming formulations - Multicoloring - Polytopes - Random instance
Descripción: This paper presents a new generalization of the graph multicoloring problem. We propose a Branch-and-Cut algorithm based on a new integer programming formulation. The cuts used are valid inequalities that we could identify to the polytope associated with the model. The Branch-and-Cut system includes separation heuristics for the valid inequalities, specific initial and primal heuristics, branching and pruning rules. We report on computational experience with random instances. © 2009 Elsevier B.V. All rights reserved.
...ver más Tipo de documento: info:ar-repo/semantics/artículo
Bonomo, F. - Marenco, J. - Saban, D. - Stier-Moses, N.E.
Discrete Appl Math 2012;160(18):2573-2590
2012
Temas: Maximum edge subgraph problem - Polyhedral combinatorics - Quasi-cliques - Branch-and-cut algorithms - Computational studies - Integer programming formulations - Polyhedral approach - Polyhedral combinatorics - Polyhedral studies - Polytopes
Descripción: The study of cohesive subgroups is an important aspect of social network analysis. Cohesive subgroups are studied using different relaxations of the notion of clique in a graph. For instance, given a graph and an integer k, the maximum edge subgraph problem consists of finding a k-vertex subset such that the number of edges within the subset is maximum. This work proposes a polyhedral approach for this NP-hard problem. We study the polytope associated to an integer programming formulation of the problem, present several families of facet-inducing valid inequalities, and discuss the separation problem associated to these families. Finally, we implement a branch and cut algorithm for this problem. This computational study illustrates the effectiveness of the classes of inequalities presented in this work. © 2011 Elsevier B.V. All rights reserved.
...ver más Tipo de documento: info:ar-repo/semantics/artículo