1,721,118 research outputs found
On the Stability Number of the Edge Intersection of Two Graphs
No full textLet G be the graph obtained as the edge intersection of two graphs G1, G2 on the same vertex set V. We show that if at least one of G1, G2 is perfect, then α(G) <= α(G1)·α(G2), where α() is the cardinality of the largest stable set. Moreover, for
general G1 and G2, we show that α(G) <= R(α(G1)+1,α(G2)+1)−1, where R(k,l) is the Ramsey number
Time dependent spatial profile of Q-switched laser pulses in a Nd:YAG loaded Gaussian reflectivity mirror unstable resonator
No full text
Bidimensional packing by bilinear programming
No full textWe consider geometric problems in which rectangles have to be packed into (identical) squares. These problems turn out to be very hard in practice, and ILP formulations in which variables specify the coordinates in the packing perform very poorly. While most methods developed so far are based on simple geometric consider- ations, a recent landmark result of Fekete and Schepers suggests to put these geometric aspects aside and use the most advanced tools for the one-dimensional case. In this paper we make additional progress in this direction, especially on the basic question “Does a given set of rectangles fit into a square?”, which turns out to be the bottleneck of all the approaches known. Given a set of rectangles and the associated convex hull of rectangle subsets that fit into a square, we derive a wide class of valid inequalities for this convex hull from a complete description of the two knapsack polytopes asso- ciated with the widths and the heights of the rectangles, respectively. In addition, we illustrate how to solve the associated separation problem as a bilinear program, for which we develop a solution method that turns out to be fast in practice, and show that the integer solutions that satisfy all these constraints generally correspond to vertices of the original convex hull for the benchmark instances in the literature. The same tools are used to derive lower bounds for the two-dimensional bin packing problem, corresponding to the determination of an optimal pair of so-called dual feasible func- tions. These lower bounds in many cases equal those obtained by the customary set covering formulation (for which column generation is very hard), but are computable within a time that is smaller by some orders of magnitude. This allows us to close a few of the benchmark instances in the literature
La giurisdizione in materia di contratti di engineering
No full textIl contributo affronta il tema dell'accertamento della giurisdizione nell'ambito di un contratto internazionale di engineering, passando in rassegna gli strumenti normativi in vigore nell'ordinamento italiano e analizzando le problematicità applicative dei titoli di giurisdizione potenzialmente rilevanti
Improving a Family of Approximation Algorithms to Edge Color Multigraphs
Full text linkGiven a multigraph G=(V,E), the Edge Coloring Problem (ECP) calls for the minimum number X of colors needed to color the edges in E so that all edges incident with a common node are assigned different colors. The best known polynomial time approximation algorithms for ECP belong to a same family, which is likely to contain, for each positive integer k, an algorithm which uses at most ((2k+1)X+(2k-2))/2k (rounded up) colors. For k<= 5 the existence of the corresponding algorithm was shown, whereas for larger values of k the question is open. We show that, for any k such that the corresponding algorithm exists, it is possible to improve the algorithm so as to use at most ((2k+1)X+(2k-3))/2k (rounded up) colors. It is easily shown that the (2k-3)/2k term cannot be reduced further, unless P=NP. We also discuss how our result can be used to extend the set of cases in which well-known conjectures on ECP are valid
Global optimization problems and domain reduction strategies
No full textIn this paper we discuss domain reduction strategies for global optimization problems with a nonconvex objective function over a bounded convex feasible region. After introducing a standard domain reduction and its iterated version, we will introduce a new reduction strategy. Under mild assumptions, we will prove the equivalence between the new domain reduction and the iterated version of the standard one, allowing a new interpretation of the latter and a new way of computing it. Finally, we prove that any ``reasonable'' domain reduction strategy is independent of the order by which variables are processed
Exact and approximate algorithms for the index selection problem in physical database design
No full text- …
