Search results for "Combinatorics"
showing 10 items of 1770 documents
A GRASP heuristic for the mixed Chinese postman problem
2002
Abstract Arc routing problems (ARPs) consist of finding a traversal on a graph satisfying some conditions related to the links of the graph. In the Chinese postman problem (CPP) the aim is to find a minimum cost tour (closed walk) traversing all the links of the graph at least once. Both the Undirected CPP, where all the links are edges that can be traversed in both ways, and the Directed CPP, where all the links are arcs that must be traversed in a specified way, are known to be polynomially solvable. However, if we deal with a mixed graph (having edges and arcs), the problem turns out to be NP -hard. In this paper, we present a heuristic algorithm for this problem, the so-called Mixed CPP…
A note on symmetry reduction for circular traveling tournament problems
2011
Abstract The traveling tournament problem (TTP) consists of finding a distance-minimal double round-robin tournament where the number of consecutive breaks is bounded. Easton et al. (2001) introduced the so-called circular TTP instances, where venues of teams are located on a circle. The distance between neighboring venues is one, so that the distance between any pair of teams is the distance on the circle. It is empirically proved that these instances are very hard to solve due to the inherent symmetry. This note presents new ideas to cut off essentially identical parts of the solution space. Enumerative solution approaches, e.g. relying on branch-and-bound, benefit from this reduction. We…
The Hierarchical Mixed Rural Postman Problem: Polyhedral analysis and a branch-and-cut algorithm
2017
[EN] The Hierarchical Mixed Rural Postman Problem is defined on a mixed graph where arcs and edges that require a service are divided into clusters' that have to be serviced in a hierarchical order. The problem generalizes the Mixed Rural Postman Problem and thus is NP-hard. In this paper, we provide a polyhedral analysis of the problem and propose a branch-and-cut algorithm for its solution based on the introduced classes of valid inequalities. Extensive computational experiments are reported on benchmark instances. The exact approach allows to find the optimal solutions in less than 1 hour for instances with up to 999 vertices, 2678 links, and five clusters.
Empirical modeling of material composition and size in MOFs prepared with ligand mixtures
2019
Systematic analyses of the composition and size of metal-organic frameworks built with Zn4O and terephthalic/amino-terephthalic acid mixtures, together with a kinetic assay, reveal how these ligands behave differently, which reveals the complexity of crystal growth in these frameworks and the ability to tune it on purpose.
La téléréalité pourrait-elle contaminer la relation commerciale sur Internet?
2012
International audience; Participer à une émission de téléréalité est une activité rémunérée. Et pourtant, il s'agit d'un jeu... Alors que penser des activités sur l'Internet ? Au départ, tout y était gratuit, ou presque. Maintenant, c'est une toute autre histoire, puisque les entreprises cherchent à y tarifer tous leurs services. Mais, à l'inverse, allons-nous voir des internautes demander à leur tour à être rémunérés pour leur participation en ligne à la création de nouveaux produits, ou au montage de nouvelles campagnes, ou toute autre activité innovatrice ? Les entreprises qui en profitent feraient bien de se le demander, car les pratiques de la téléréalité pourraient bien faire des émul…
Minimal star-varieties of polynomial growth and bounded colength
2018
Abstract Let V be a variety of associative algebras with involution ⁎ over a field F of characteristic zero. Giambruno and Mishchenko proved in [6] that the ⁎-codimension sequence of V is polynomially bounded if and only if V does not contain the commutative algebra D = F ⊕ F , endowed with the exchange involution, and M , a suitable 4-dimensional subalgebra of the algebra of 4 × 4 upper triangular matrices , endowed with the reflection involution. As a consequence the algebras D and M generate the only varieties of almost polynomial growth. In [20] the authors completely classify all subvarieties and all minimal subvarieties of the varieties var ⁎ ( D ) and var ⁎ ( M ) . In this paper we e…
Polynomial growth and star-varieties
2016
Abstract Let V be a variety of associative algebras with involution over a field F of characteristic zero and let c n ⁎ ( V ) , n = 1 , 2 , … , be its ⁎-codimension sequence. Such a sequence is polynomially bounded if and only if V does not contain the commutative algebra F ⊕ F , endowed with the exchange involution, and M, a suitable 4-dimensional subalgebra of the algebra of 4 × 4 upper triangular matrices. Such algebras generate the only varieties of ⁎-algebras of almost polynomial growth, i.e., varieties of exponential growth such that any proper subvariety is polynomially bounded. In this paper we completely classify all subvarieties of the ⁎-varieties of almost polynomial growth by gi…
Star-group identities and groups of units
2010
Analogous to *-identities in rings with involution we define *-identities in groups. Suppose that G is a torsion group with involution * and that F is an infinite field with char F ≠ 2. Extend * linearly to FG. We prove that the unit group \({\mathcal{U}}\) of FG satisfies a *-identity if and only if the symmetric elements \({\mathcal{U}^+}\) satisfy a group identity.
On minimal ∗-identities of matrices∗
1995
Let Mn (F) be the algebra of n×n matrices (n≥2) over a field F of characteristic different from 2 and let ∗ be an involution in Mn (F) In case ∗ is the transpose involution, we construct a multilinear ∗ polynomial identify of Mn (F) of degree 2n−1, P 2n−1(k 1, s 2, … s 2n−1) in one skew variable and the remaining symmetric variables of minimal degree among all ∗-polynomial identities of this type. We also prove that any other multilinear ∗-polynomial identity of Mn (F) of this type of degree 2n−1 is a scalar multiple of P2n−1 . In case ∗ is the symplectic involution in Mn (F), we construct a ∗-polynomial identity of Mn (F) of degree 2n−1 in skew variables T2n−1 (k 1,…,k 2n−1) and we prove t…
Superalgebras with Involution or Superinvolution and Almost Polynomial Growth of the Codimensions
2018
Let A be a superalgebra with graded involution or superinvolution ∗ and let $c_{n}^{*}(A)$, n = 1,2,…, be its sequence of ∗-codimensions. In case A is finite dimensional, in Giambruno et al. (Algebr. Represent. Theory 19(3), 599–611 2016, Linear Multilinear Algebra 64(3), 484–501 2016) it was proved that such a sequence is polynomially bounded if and only if the variety generated by A does not contain the group algebra of $\mathbb {Z}_{2}$ and a 4-dimensional subalgebra of the 4 × 4 upper-triangular matrices with suitable graded involutions or superinvolutions. In this paper we study the general case of ∗-superalgebras satisfying a polynomial identity. As a consequence we classify the varie…