A distance constrainedp-facility location problem on the real line

LetV = {v ₁,, v _n } be a set ofn points on the real line (existing facilities). The problem considered is to locatep new point facilities,F ₁,, F _p , inV while satisfying distance constraints between pairs of existing and new facilities and between pairs of new facilities. Fori = 1, , p, j = 1, , n, the cost of locatingF _i at pointv _j isc _ij . The objective is to minimize the total cost of setting up the new facilities. We present anO(p ³ n ² logn) algorithm to solve the model.     

A constant factor approximation algorithm for the fault-tolerant facility location problem

We consider a generalization of the classical facility location problem, where we require the solution to be fault-tolerant. In this generalization, every demand point j must be served by r_j facilities instead of just one. The facilities other than the closest one are “backup” facilities for that demand, and any such facility will be used only if all closer facilities (or the links to them) fail. Hence, for any demand point, we can assign nonincreasing weights to the routing costs to farther facilities. The cost of assignment for demand j is the weighted linear combination of the assignment costs to its r_j closest open facilities. We wish to minimize the sum of the cost of opening the facilities and the assignment cost of each demand j. We obtain a factor 4 approximation to this problem through the application of various rounding techniques to the linear relaxation of an integer program formulation. We further improve the approximation ratio to 3.16 using randomization and to 2.41 using greedy local-search type techniques.     

On the ( r | X p )-Medianoid Problem on a Network with Vertex and Edge Demands

This article considers the (r|X _p )-medianoid problem on a network N=(V,E) with vertex and edge demands. There are already p facilities located on the network and customers patronize the closest facility. The aim is to locate r additional facilities on the network where their captured demands will be maximized. Relationships with the (r|X _p )-medianoid problem with vertex demands are established. Complexity and algorithmic results are presented.     

Discretization and resolution of the (<Emphasis Type="Italic">r</Emphasis>|<Emphasis Type="Italic">X</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis></Subscript>)-medianoid problem involving quality criteria

In this paper an extension of the (r|X _p )-medianoid on networks introduced by Hakimi (1983) is studied. In this extension the customer considers not only the distance but some characteristics of the facilities such as store size, quality of service and parking space. A new firm wants to establishr new facilities which have to compete with thep facilities that already exist in the market. The entry firm wants to find their locations and characteristics to maximize profits. Three different customer choice rules (binary, partially binary and proportional preferences) are considered. Some discretization results are obtained and a resolution procedure is proposed. The problem is solved combining a global search algorithm based on a branch and bound procedure with some combinatorial heuristics (greedy, interchange, and tabu search). Some computational experiences are presented. Partially supported by Ministerio de Ciencia y Tecnología (Spain) and FEDER, grant BFM2002-04525-C02-01.     

Line-graphical degree sequences

A degree sequence π = (d₁, d₂,…,d_p), with d₁ ≥ d₂ ≥…≥ d_p, is line graphical if it is realized by the line graph of some graph. Degree sequences with line-graphical realizations are characterized for the cases d₁ = p - 1, d₁ = p - 2, d₁ ≤ 3, and d₁ = d_p. It is also shown that if a degree sequence with d₁ = p-1 is line graphical, it is uniquely line graphical. It follows that with possibly one exception each line-graphical realization of an arbitrary degree sequence must have either C₅, 2K₁, + K₂, K₁ + 2K₂, or 3K₁, as an induced subgraph.     

Die Konstruktion der mittleren Linie bei Oberflächenprofilen und einige Zusammenhänge zwischen den zur Kennzeichnung von Oberflächen benutzten Grössen

Summary Attention is directed first to the analogy between the problem of evaluating collectives and that of finding a numerical expression for an existing surface.For the valueh _RMS /h _AVE , approximations are made using Fourier series of the surface profil based on the center line.h _AVE =center line average (=h _CLA ). Forh _AVE , an upper bound calculated from the Fourier coefficients is stated. With this, and ash _RMS may be determined in a definite form, a lower bound forh _RMS /h _AVE is obtained. Provided that the surface profil is the superimposition of two harmonics, a lower, bound forh _AVE and then an upper bound forh _RMS /h _AVE could be found. In order to get a base line for which the areas embraced by the profile above and below the line are equal and a minimum, a graphical method is constructed.

---

---

Mitteilung aus der Physikalisch-Technischen Bundesanstalt.     

A new bounding method for single facility location models

This paper develops a new lower bound for single facility location problems withl _p distances. We prove that the method produces superior results to other known procedures. The new bound is also computationally efficient. Numerical results are given for a range of examples with varying numbers of existing facilities andp values.     

Collinear periodic cracks and/or rigid line inclusions ofantiplane sliding mode in one-dimensional hexagonal quasicrystal

For a one-dimensional (1D) hexagonal quasicrystal (QC), there is the periodic (x₁,x₂)-plane of atomic structures with the quasiperiodic direction x₃-axis along which there exists a phason displacement. The macroscopically collinear periodic cracks and/or rigid line inclusions are placed on the periodic (x₁,x₂)-plane for finding out the influence of phason displacement on the related physical quantities. These two models are reduced to the Riemann–Hilbert problem of periodic analytic functions to obtain the closed-form solutions for the antiplane sliding mode. It is found that the phonon and phason stress intensity factors of cracks as well as the phonon and phason stress field intensity factors of rigid line inclusions are not related to the coupling of phonon and phason fields. These mean that there is not the influence of phason displacement on both the phonon stress intensity factor (usual stress intensity factor) of cracks and the phonon stress field intensity factor of rigid line inclusions. However, the energy release rates of periodic cracks and/or rigid line inclusions are obtained and affected not only by the periodicity of cracks and/or rigid line inclusions but also by the phason displacement.     

Geometrical and physical interpretation of evolution governed by general complex algebra

In this paper we explore a geometrical and physical matter of the evolution governed by the generator of General Complex Algebra, GC₂. The generator of this algebra obeys a quadratic polynomial equation. It is shown that the geometrical image of the GC₂-number is given by a straight line fixed by two given points on Euclidean plane. In this representation the straight line possesses the norm and the argument. The motion of the straight line conserving the norm of the line is described by evolution equation governed by the generator of the GC₂-algebra. This evolution is depicted on the Euclidean plane as rotational motion of the straight line around the semicircle to which this line is tangent. Physical interpretation is found within the framework of the relativistic dynamics where the quadratic polynomial is formed by mass-shell equation. In this way we come to a new representation for the momenta of the relativistic particle.     

A Helly-Type Theorem for Line Transversals to Disjoint Unit Balls

   Abstract. Let F be a family of disjoint unit balls in R ³ . We prove that there is a Helly-number n ₀ ≤ 46 , such that if every n ₀ members of F ( | F | ≥ n ₀ ) have a line transversal, then F has a line transversal. In order to prove this we prove that if the members of F can be ordered in a way such that every 12 members of F are met by a line consistent with the ordering, then F has a line transversal. The proof also uses the recent result on geometric permutations for disjoint unit balls by Katchalski, Suri, and Zhou.     

A maximum trip covering location problem with an alternative mode of transportation on tree networks and segments

In this paper the following facility location problem in a mixed planar-network space is considered: We assume that traveling along a given network is faster than traveling within the plane according to the Euclidean distance. A pair of points (A _i ,A _j ) is called covered if the time to access the network from A _i plus the time for traveling along the network plus the time for reaching A _j is lower than, or equal to, a given acceptance level related to the travel time without using the network. The objective is to find facilities (i.e. entry and exit points) on the network that maximize the number of covered pairs. We present a reformulation of the problem using convex covering sets and use this formulation to derive a finite dominating set and an algorithm for locating two facilities on a tree network. Moreover, we adapt a geometric branch and bound approach to the discrete nature of the problem and suggest a procedure for locating more than two facilities on a single line, which is evaluated numerically.     

Remarks on nonmeasurable unions of big point families

We show that under some conditions on a family A ? I there exists a subfamily A₀ ? A such that ∪ A₀ is nonmeasurable with respect to a fixed ideal I with Borel base of a fixed uncountable Polish space. Our result applies to the classical ideal of null subsets of the real line and to the ideal of first category subsets of the real line (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

A Helly-Type Theorem for Line Transversals to Disjoint Unit Balls

Abstract. Let F be a family of disjoint unit balls in R ³ . We prove that there is a Helly-number n ₀ ≤ 46 , such that if every n ₀ members of F ( | F | ≥ n ₀ ) have a line transversal, then F has a line transversal. In order to prove this we prove that if the members of F can be ordered in a way such that every 12 members of F are met by a line consistent with the ordering, then F has a line transversal. The proof also uses the recent result on geometric permutations for disjoint unit balls by Katchalski, Suri, and Zhou.     

Delaying satisfiability for random 2SAT

Let (C₁,C′_(*)),(C₂,C′_(*)),…,(C _m,C′_(*)) be a sequence of ordered pairs of 2CNF clauses chosen uniformly at random (with replacement) from the set of all 4 \begin{align*}\binom{n}{2}\end{align*} clauses on n variables. Choosing exactly one clause from each pair defines a probability distribution over 2CNF formulas. The choice at each step must be made on‐line, without backtracking, but may depend on the clauses chosen previously. We show that there exists an on‐line choice algorithm in the above process which results whp in a satisfiable 2CNF formula as long as m/n ≤ (1000/999)^1/4. This contrasts with the well‐known fact that a random m ‐clause formula constructed without the choice of two clauses at each step is unsatisfiable whp whenever m/n > 1. Thus the choice algorithm is able to delay satisfiability of a random 2CNF formula beyond the classical satisfiability threshold. Choice processes of this kind in random structures are known as “Achlioptas processes.” This paper joins a series of previous results studying Achlioptas processes in different settings, such as delaying the appearance of a giant component or a Hamilton cycle in a random graph. In addition to the on‐line setting above, we also consider an off‐line version in which all m clause‐pairs are presented in advance, and the algorithm chooses one clause from each pair with knowledge of all pairs. For the off‐line setting, we show that the two‐choice satisfiability threshold for k ‐SAT for any fixed k coincides with the standard satisfiability threshold for random 2k ‐SAT.© 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

Two storage inventory model with fuzzy deterioration over a random planning horizon

An inventory model for a deteriorating item with stock dependent demand is developed under two storage facilities over a random planning horizon, which is assumed to follow exponential distribution with known parameter. For crisp deterioration rate, the expected profit is derived and maximized via genetic algorithm (GA). On the other hand, when deterioration rate is imprecise then optimistic/pessimistic equivalent of fuzzy objective function is obtained using possibility/necessity measure of fuzzy event. Fuzzy simulation process is proposed to maximize the optimistic/pessimistic return and finally fuzzy simulation-based GA is developed to solve the model. The models are illustrated with some numerical data. Sensitivity analyses on expected profit function with respect to distribution parameter λ and confidence levels α₁ and α₂ are also presented.     

Hyperflock determining line sets and totally regular parallelisms of PG (3, \mathbbR){(3,\,{\mathbb{R}})}

By a totally regular parallelism of the real projective 3-space P₃:=PG(3, \mathbb R){\Pi_3:={{\rm PG}}(3, \mathbb {R})} we mean a family T of regular spreads such that each line of Π ₃ is contained in exactly one spread of T. For the investigation of totally regular parallelisms the authors mainly employ Klein’s correspondence λ of line geometry and the polarity π ₅ associated with the Klein quadric H ₅ (for details see Chaps. 1 and 3). The λ-image of a totally regular parallelism T is a hyperflock of H ₅, i.e., a family H of elliptic subquadrics of H ₅ such that each point of H ₅ is on exactly one subquadric of H. Moreover, {p₅(span  l(X))|X ? T}=:H_T{\{\pi_5({{\rm span}} \,\lambda(\mathcal {X}))\vert\mathcal {X}\in\bf{T}\}=:\mathcal {H}_{\bf{T}}} is a hyperflock determining line set, i.e., a set Z{\mathcal {Z}} of 0-secants of H ₅ such that each tangential hyperplane of H ₅ contains exactly one line of Z{\mathcal {Z}} . We say that dim(span H_T)=:d_T{{{\rm dim}}({{\rm span}}\,\mathcal {H}_{\bf{T}})=:d_{\bf{T}}} is the dimension of T and that T is a d _T - parallelism. Clifford parallelisms and 2-parallelisms coincide. The examples of non-Clifford parallelisms exhibited in Betten and Riesinger [Result Math 47:226–241, 2004; Adv Geom 8:11–32, 2008; J Geom (to appear)] are totally regular and of dimension 3. If G{\mathcal{G}} is a hyperflock determining line set, then {l^-1 (p₅(X) ?H₅) | X ? G}{\{\lambda^{-1}\,{\rm (}\pi_5(X){\,\cap H_5)\,|\, X\in\mathcal{G}\}}} is a totally regular parallelism. In the present paper the authors construct examples of topological (see Definition 1.1) 4- and 5-parallelisms via hyperflock determining line sets.     

Nondegenerate cohomology pairing for transitive Lie algebroids,characterization

The Evens-Lu-Weinstein representation (Q _A , D) for a Lie algebroid A on a manifold M is studied in the transitive case. To consider at the same time non-oriented manifolds as well, this representation is slightly modified to (Q _A ^or , D^or) by tensoring by orientation flat line bundle, Q _A ^or =Q_A⊗or (M) and D ^or=D⊗∂ _A ^or . It is shown that the induced cohomology pairing is nondegenerate and that the representation (Q _A ^or , D^or) is the unique (up to isomorphy) line representation for which the top group of compactly supported cohomology is nontrivial. In the case of trivial Lie algebroid A=TM the theorem reduce to the following: the orientation flat bundle (or (M), ∂ _A ^or ) is the unique (up to isomorphy) flat line bundle (ξ, ∇) for which the twisted de Rham complex of compactly supported differential forms on M with values in ξ possesses the nontrivial cohomology group in the top dimension. Finally it is obtained the characterization of transitive Lie algebroids for which the Lie algebroid cohomology with trivial coefficients (or with coefficients in the orientation flat line bundle) gives Poincaré duality. In proofs of these theorems for Lie algebroids it is used the Hochschild-Serre spectral sequence and it is shown the general fact concerning pairings between graded filtered differential ℝ-vector spaces: assuming that the second terms live in the finite rectangular, nondegeneration of the pairing for the second terms (which can be infinite dimensional) implies the same for cohomology spaces.     

图和线图的谱性质

Let G be a simple connected graph with n vertices and m edges,Lo be the line graph of G and λ1(LG)≥λ2 (LG)≥...≥λm(LG) be the eigenvalues of the graph LG,.. In this paper, the range of eigenvalues of a line graph is considered. Some sharp upper bounds and sharp lower bounds of the eigenvalues of Lc. are obtained. In oarticular,it is oroved that-2cos(π/n)≤λn-1(LG)≤n-4 and λn(LG)=-2 if and only if G is bipartite.     

Hadwiger's conjecture for quasi‐line graphs

A graph G is a quasi‐line graph if for every vertex v ∈ V(G), the set of neighbors of v in G can be expressed as the union of two cliques. The class of quasi‐line graphs is a proper superset of the class of line graphs. Hadwiger's conjecture states that if a graph G is not t‐colorable then it contains K_{t + 1} as a minor. This conjecture has been proved for line graphs by Reed and Seymour. We extend their result to all quasi‐line graphs. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 17–33, 2008