Pareto memetic algorithm with path relinking for bi-objective traveling salesperson problem

The paper presents an effective version of the Pareto memetic algorithm with path relinking and efficient local search for multiple objective traveling salesperson problem. In multiple objective Traveling salesperson problem (TSP), multiple costs are associated with each arc (link). The multiple costs may for example correspond to the financial cost of travel along a link, time of travel, or risk in the case of hazardous materials. The algorithm searches for new good solutions along paths in the decision space linking two other good solutions selected for recombination. Instead of a simple local search it uses short runs of tabu search based on the steepest version of the Lin–Kernighan algorithm. The efficiency of local search is further improved by the techniques of candidate moves and locked arcs. In the final step of the algorithm the neighborhood of each potentially Pareto-optimal solution is searched for new solutions that could be added to this set. The algorithm is compared experimentally to the state-of-the-art algorithms for multiple objective TSP.     

Computation of the center and diameter of outerplanar graphs

The center of a graph is the set of vertices with minimum eccentricity. An outerplanar graph is a planar segmentation of a polygon. We define a notion of edge eccentricities for the edges of an outerplanar graph. We present an algorithm which efficiently computes these edge eccentricities. Knowledge of the edge eccentricities allows subsequent linear time computation of the center and diameter of outerplanar graphs. The computation of edge eccentricities is shown to require linear time for certain subclasses of outerplanar graphs.     

Stratified two-stage sampling in domains: Sample allocation between domains, strata, and sampling stages

In the paper, formulae for optimum sample allocation between domains, strata in the domains, and sampling stages are presented for stratified two-stage sampling in domains under fixed sample size of SSUs from PSUs.     

Generating ultrafilters in a reasonable way

We continue investigations of reasonable ultrafilters on uncountable cardinals defined in Shelah [8]. We introduce a general scheme of generating a filter on λ from filters on smaller sets and we investigate the combinatorics of objects obtained this way. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On the Jacobian Newton polygon of plane curve singularities

We investigate the Jacobian Newton polygon of plane curve singularities. This invariant was introduced by Teissier in the more general context of hypersurfaces. The Jacobian Newton polygon determines the topological type of a branch (Merle’s result) but not of an arbitrary reduced curve (Eggers example). Our main result states that the Jacobian Newton Polygon determines the topological type of a non-degenerate unitangent singularity. The Milnor number, the Łojasiewicz exponent, the Hironaka exponent of maximal contact and the number of tangents are examples of invariants that can be calculated by means of the Jacobian Newton polygon. We show that the number of branches and the Newton number defined by Oka do not have this property. Dedicated to Professor Arkadiusz Płoski on his 60th birthday     

The Deletion Method For Upper Tail Estimates

We present a new method to show concentration of the upper tail of random variables that can be written as sums of variables with plenty of independence. We compare our method with the martingale method by Kim and Vu, which often leads to similar results.Some applications are given to the number X _G of copies of a graph G in the random graph (n,p). In particular, for G = K ₄ and G = C ₄ we improve the earlier known upper bounds on —ln (X _G 2 X _G ) in some range of p = p(n).* Research of the second author supported by KBN grants 2 P03A 032 16 and 2 P03A 015 23.     

Strong edge colorings of uniform graphs

For a graph G=(V(G),E(G)), a strong edge coloring of G is an edge coloring in which every color class is an induced matching. The strong chromatic index of G, χ_s(G), is the smallest number of colors in a strong edge coloring of G. The strong chromatic index of the random graph G(n,p) was considered in Discrete Math. 281 (2004) 129, Austral. J. Combin. 10 (1994) 97, Austral. J. Combin. 18 (1998) 219 and Combin. Probab. Comput. 11 (1) (2002) 103. In this paper, we consider χ_s(G) for a related class of graphs G known as uniform or ε-regular graphs. In particular, we prove that for 0<ε?d<1, all (d,ε)-regular bipartite graphs G=(U∪V,E) with |U|=|V|?n₀(d,ε) satisfy χ_s(G)?ζ(ε)Δ(G)², where ζ(ε)→0 as ε→0 (this order of magnitude is easily seen to be best possible). Our main tool in proving this statement is a powerful packing result of Pippenger and Spencer (Combin. Theory Ser. A 51(1) (1989) 24).