Search results for "Combinatorics"
showing 10 items of 1770 documents
Structural study, thermal expansion and electrical conductivity of the composition NaSnZr(PO4)3
1993
Abstract The structure of the composition NaSnZr(PO4)3 and its evolution with temperature has been studied. The structure presents the space group R 3 c. The refinement of the structure shows that the Sn and Zr atoms are statistically distributed over the same crystallographic position. The unit cell expands in the c direction and contracts in the a direction, remaining the space group R 3 c at temperatures between 26 and 1000°C. The low value of the electrical conductivity at 400°C, 5.729×10−7S/cm and the low density of the pellets limited the use as electrical conductor.
On the population model with a sine function
2006
In the interval [0,1] function sr(x) = r sin πx behaves similar to logistic function h μ (x) = μx(1‐ x). We prove that for every r > there exists subset ? ⊂ [0,1] such that sr : ? → ? is a chaotic function. Since the logistic function is chaotic in another subset of [0,1] but both functions have similar graphs in [0,1] we conclude that it can lead to errors in practice. First Published Online: 14 Oct 2010
Curves with no tritangent planes in space and their convex envelopes
1990
M. H. Freedman ([3]) proved that for a generic subset of closed curves in ~ 3 with nonvanishing curvature and torsion the number of t r i tangent planes is even and finite. He also guessed, for each even number s _> 0, the existence of an open subset A8 of closed curves with nonvanishing curvature and torsion such tha t each curve in A8 has exact ly s t r i t angent planes. A question tha t can be asked in this context is: Which curves with nonvanishing curvature and torsion have no t r i tangent planes? An example of such a curve is given by the (1,2)-curve on the torus with rat io a, 3 < a < 5 (see [2]). For a generi c curve, we give a pa r t i a l answer to this question here by finding …
The guarded fragment with transitive guards
2004
The guarded fragment with transitive guards, (GF+TG), is an extension of the guarded frag- ment of 9rst-order logic, GF, in which certain predicates are required to be transitive, transitive predicate letters appear only in guards of the quanti9ers and the equality symbol may appear everywhere. We prove that the decision problem for (GF+TG) is decidable. Moreover, we show that the problem is in 2EXPTIME. This result is optimal since the satis9ability problem for GF is 2EXPTIME-complete (J. Symbolic Logic 64 (1999) 1719-1742). We also show that the satis- 9ability problem for two-variable (GF+TG) is NEXPTIME-hard in contrast to GF with bounded number of variables for which the satis9ability …
An ILS-Based Metaheuristic for the Stacker Crane Problem
2012
[EN] In this paper we propose a metaheuristic algorithm for the Stacker Crane Problem. This is an NP-hard arc routing problem whose name derives from the practical problem of operating a crane. Here we present a formulation and a lower bound for this problem and propose a metaheuristic algorithm based on the combination of a Multi-start and an Iterated Local Search procedures. Computational results on a large set of instances are presented.
Self-stabilizing Balls & Bins in Batches
2016
A fundamental problem in distributed computing is the distribution of requests to a set of uniform servers without a centralized controller. Classically, such problems are modelled as static balls into bins processes, where m balls (tasks) are to be distributed to n bins (servers). In a seminal work, [Azar et al.; JoC'99] proposed the sequential strategy Greedy[d] for n = m. When thrown, a ball queries the load of d random bins and is allocated to a least loaded of these. [Azar et al.; JoC'99] showed that d=2 yields an exponential improvement compared to d=1. [Berenbrink et al.; JoC'06] extended this to m ⇒ n, showing that the maximal load difference is independent of m for d=2 (in contrast…
Handling precedence constraints in scheduling problems by the sequence pair representation
2015
In this paper, we show that sequence pair (SP) representation, primarily applied to the rectangle packing problems appearing in the VLSI industry, can be a solution representation of precedence constrained scheduling. We present three interpretations of sequence pair, which differ in complexity of schedule evaluation and size of a corresponding solution space. For each interpretation we construct an incremental precedence constrained SP neighborhood evaluation algorithm, computing feasibility of each solution in the insert neighborhood in an amortized constant time per examined solution, and prove the connectivity property of the considered neighborhoods. To compare proposed interpretations…
An experimental study of the stability problem in discrete tomography
2003
This paper introduces the topic of discrete tomography, briefly showing its main applications, algorithms and new prospects of research. It focuses on the still open problem of stability, facing it from an experimental point of view. In particular an extensive simulation lets verify the robustness of a well known reconstruction technique for binary convex objects, calculating the probability of finding solutions compatible with a given set of noisy projections. © 2005 Elsevier Ltd. All rights reserved.
On the Bias and Performance of the Edge-Set Encoding
2009
The edge-set encoding of trees directly represents trees as sets of their edges. Nonheuristic operators for edge-sets manipulate trees' edges without regard for their weights, while heuristic operators consider edges' weights when including or excluding them. In the latter case, the operators generally favor edges with lower weights, and they tend to generate trees that resemble minimum spanning trees. This bias is strong, which suggests that evolutionary algorithms (EAs) that employ heuristic operators will succeed when optimum solutions resemble minimum spanning trees (MSTs) but fail otherwise. The one-max tree problem is a scalable test problem for trees where the optimum solution can be…
Upper and lower bounds for the vehicle-routing problem with private fleet and common carrier
2019
Abstract The vehicle-routing problem with private fleet and common carrier (VRPPC) extends the capacitated VRP by considering the option of outsourcing customers to subcontractors at a customer-dependent cost instead of serving them with the private fleet. The VRPPC has important applications in small package shipping and manufacturing, but despite its relevance, no exact solution approach has been introduced so far. We propose a branch-price-and-cut algorithm that is able to solve small to medium-sized instances and provides tight lower bounds for larger instances from the literature. In addition, we develop a large neighborhood search that shows a decent solution quality and competitive r…