Heuristic algorithms for general <Emphasis Type="Italic">k</Emphasis>-level facility location problems

In a general k-level uncapacitated facility location problem (k-GLUFLP), we are given a set of demand points, denoted by D, where clients are located. Facilities have to be located at a given set of potential sites, which is denoted by F in order to serve the clients. Each client needs to be served by a chain of k different facilities. The problem is to determine some sites of F to be set up and to find an assignment of each client to a chain of k facilities so that the sum of the setup costs and the shipping costs is minimized. In this paper, for a fixed k, an approximation algorithm within a factor of 3 of the optimum cost is presented for k-GLUFLP under the assumption that the shipping costs satisfy the properties of metric space. In addition, when no fixed cost is charged for setting up the facilities and k=2, we show that the problem is strong NP-complete and the constant approximation factor is further sharpen to be 3/2 by a simple algorithm. Furthermore, it is shown that this ratio analysis is tight.     

Some notes on graphs whose index is close to 2

We consider two classes of graphs: (i) trees of order n and diameter d =n − 3 and (ii) unicyclic graphs of order n and girth g = n − 2. Assuming that each graph within these classes has two vertices of degree 3 at distance k, we order by the index (i.e. spectral radius) the graphs from (i) for any fixed k (1 ? k ? d − 2), and the graphs from (ii) independently of k.     

The signless Laplacian spectral radius of tricyclic graphs and trees with k pendant vertices

In this paper, we consider the following problem: of all tricyclic graphs or trees of order n with k pendant vertices (n,k fixed), which achieves the maximal signless Laplacian spectral radius?We determine the graph with the largest signless Laplacian spectral radius among all tricyclic graphs with n vertices and k pendant vertices. Then we show that the maximal signless Laplacian spectral radius among all trees of order n with k pendant vertices is obtained uniquely at T_n,k, where T_n,k is a tree obtained from a star K_1,k and k paths of almost equal lengths by joining each pendant vertex to one end-vertex of one path. We also discuss the signless Laplacian spectral radius of T_n,k and give some results.     

Approximability of single machine scheduling with fixed jobs to minimize total completion time

We consider the single machine scheduling problem to minimize total completion time with fixed jobs, precedence constraints and release dates. There are some jobs that are already fixed in the schedule. The remaining jobs are free to be assigned to any free-time intervals on the machine in such a way that they do not overlap with the fixed jobs. Each free job has a release date, and the order of processing the free jobs is restricted by the given precedence constraints. The objective is to minimize the total completion time. This problem is strongly NP-hard. Approximability of this problem is studied in this paper. When the jobs are processed without preemption, we show that the problem has a linear-time n-approximation algorithm, but no pseudopolynomial-time (1 − δ)n-approximation algorithm exists even if all the release dates are zero, for any constant δ > 0, if P ≠ NP, where n is the number of jobs; for the case that the jobs have no precedence constraints and no release dates, we show that the problem has no pseudopolynomial-time (2 − δ)-approximation algorithm, for any constant δ > 0, if P ≠ NP, and for the weighted version, we show that the problem has no polynomial-time 2^q(n)-approximation algorithm and no pseudopolynomial-time q(n)-approximation algorithm, where q(n) is any given polynomial of n. When preemption is allowed, we show that the problem with independent jobs can be solved in O(n log n) time with distinct release dates, but the weighted version is strongly NP-hard even with no release dates; the problems with weighted independent jobs or with jobs under precedence constraints are shown having polynomial-time n-approximation algorithms. We also establish the relationship of the approximability between the fixed job scheduling problem and the bin-packing problem.     

Flip Graphs of Bounded Degree Triangulations

We study flip graphs of triangulations whose maximum vertex degree is bounded by a constant k. In particular, we consider triangulations of sets of n points in convex position in the plane and prove that their flip graph is connected if and only if k > 6; the diameter of the flip graph is O(n ²). We also show that, for general point sets, flip graphs of pointed pseudo-triangulations can be disconnected for k ≤ 9, and flip graphs of triangulations can be disconnected for any k. Additionally, we consider a relaxed version of the original problem. We allow the violation of the degree bound k by a small constant. Any two triangulations with maximum degree at most k of a convex point set are connected in the flip graph by a path of length O(n log n), where every intermediate triangulation has maximum degree at most k + 4.     

A k-product uncapacitated facility location problem

A k-product uncapacitated facility location problem can be described as follows. There is a set of demand points where clients are located and a set of potential sites where facilities of unlimited capacities can be set up. There are k different kinds of products. Each client needs to be supplied with k kinds of products by a set of k different facilities and each facility can be set up to supply only a distinct product with a non-negative fixed cost determined by the product it intends to supply. There is a non-negative cost of shipping goods between each pair of locations. These costs are assumed to be symmetric and satisfy the triangle inequality. The problem is to select a set of facilities to be set up and their designated products and to find an assignment for each client to a set of k   facilities so that the sum of the setup costs and the shipping costs is minimized. In this paper, an approximation algorithm within a factor of 2k+1$2k+1$ of the optimum cost is presented. Assuming that fixed setup costs are zero, we give a 2k-1$2k-1$ approximation algorithm for the problem. In addition we show that for the case k=2$k=2$, the problem is NP-complete when the cost structure is general and there is a 2-approximation algorithm when the costs are symmetric and satisfy the triangle inequality. The algorithm is shown to produce an optimal solution if the 2-product uncapacitated facility location problem with no fixed costs happens to fall on a tree graph.     

Geometric separation and exact solutions for the parameterized independent set problem on disk graphs

We consider the parameterized problem, whether for a given set  of n disks (of bounded radius ratio) in the Euclidean plane there exists a set of k non-intersecting disks. For this problem, we expose an algorithm running in time that is—to our knowledge—the first algorithm with running time bounded by an exponential with a sublinear exponent. For λ-precision disk graphs of bounded radius ratio, we show that the problem is fixed parameter tractable with a running time  . The results are based on problem kernelization and a new “geometric ( -separator) theorem” which holds for all disk graphs of bounded radius ratio. The presented algorithm then performs, in a first step, a “geometric problem kernelization” and, in a second step, uses divide-and-conquer based on our new “geometric separator theorem.”     

Intersection theorems under dimension constraints

In Ahlswede et al. [Discrete Math. 273(1-3) (2003) 9-21] we posed a series of extremal (set system) problems under dimension constraints. In the present paper, we study one of them: the intersection problem. The geometrical formulation of our problem is as follows. Given integers 0?t, k?n determine or estimate the maximum number of (0,1)-vectors in a k-dimensional subspace of the Euclidean n-space Rⁿ, such that the inner product (“intersection”) of any two is at least t. Also we are interested in the restricted (or the uniform) case of the problem; namely, the problem considered for the (0,1)-vectors of the same weight ω.The paper consists of two parts, which concern similar questions but are essentially independent with respect to the methods used.In Part I, we consider the unrestricted case of the problem. Surprisingly, in this case the problem can be reduced to a weighted version of the intersection problem for systems of finite sets. A general conjecture for this problem is proved for the cases mentioned in Ahlswede et al. [Discrete Math. 273(1-3) (2003) 9-21]. We also consider a diametric problem under dimension constraint.In Part II, we study the restricted case and solve the problem for t=1 and k<2ω, and also for any fixed 1?t?ω and k large.     

On the roots of polynomials with concentration at low degrees

We investigate the roots of polynomials with concentration at low degrees, and prove that there is an open disk, the radius of which depends only on d and k, such that any polynomial with concentration d at degree k has at most k roots in this disk. We also give numerical estimates for this radius.     

Deconstructing Approximate Offsets

We consider the offset-deconstruction problem: Given a polygonal shape?Q with n vertices, can it be expressed, up to a tolerance??? in Hausdorff distance, as the Minkowski sum of another polygonal shape P with a disk of fixed radius? If it does, we also seek a preferably simple-looking solution?P; then, P??s offset constitutes an accurate, vertex-reduced, and smoothened approximation of Q. We give an O(nlogn)-time exact decision algorithm that handles any polygonal shape, assuming the real-RAM model of computation. A variant of the algorithm, which we have implemented using the cgal library, is based on rational arithmetic and answers the same deconstruction problem up to an uncertainty parameter ??; its running time additionally depends on ??. If the input shape is found to be approximable, this algorithm also computes an approximate solution for the problem. It also allows us to solve parameter-optimization problems induced by the offset-deconstruction problem. For convex shapes, the complexity of the exact decision algorithm drops to O(n), which is also the time required to compute a solution?P with at most one more vertex than a vertex-minimal one.     

A branch-and-bound method for the minimum k−enclosing ball problem

The minimum k-enclosing ball problem seeks the ball with smallest radius that contains at least k of m given points. This problem is NP-hard. We present a branch-and-bound algorithm on the tree of the subsets of k points to solve this problem. Our method is able to solve the problem exactly in a short amount of time for small and medium sized datasets.     

Three limit theorems for vacancy in multivariate coverage problems

Three limit theorems describing asymptotic distribution of vacancy in general multivariate coverage problems are proved, in which nk-dimensional spheres are distributed within a k-dimensional unit cube according to a density f. The first result (a central limit theorem) describes the case where the proportion of vacancy converges to a fixed constant lying between 0 and 1. The last two results treat the case where the proportion of vacancy tends to 1 as n → ∞. Results of this nature have hitherto been available only for restricted k and/or for f equal to the uniform density.     

The problem of a minimal ball enclosing <Emphasis Type="Italic">k</Emphasis> points

Under study is the problem of finding a ball of minimal radius enclosing at least k points of a given finite set in a Euclidean space. In the case of a fixed dimension of the space this problem is polynomially solvable, but in general its complexity has not been previously determined. We prove that the problem is NP-hard in the strong sense and obtain a polynomial-time approximation scheme (PTAS) that enables us to solve the problem with an arbitrary relative error ? in time \(O(n^{1/\varepsilon ^2 + 1} d)\), where n is the cardinality of the original set and d is the space dimension.     

On the signless Laplacian spectral radius of graphs with cut vertices

In this paper, we show that among all the connected graphs with n vertices and k cut vertices, the maximal signless Laplacian spectral radius is attained uniquely at the graph G_n,k, where G_n,k is obtained from the complete graph K_n-k by attaching paths of almost equal lengths to all vertices of K_n-k. We also give a new proof of the analogous result for the spectral radius of the connected graphs with n vertices and k cut vertices (see [A. Berman, X.-D. Zhang, On the spectral radius of graphs with cut vertices, J. Combin. Theory Ser. B 83 (2001) 233-240]). Finally, we discuss the limit point of the maximal signless Laplacian spectral radius.     

A max version of the generalized spectral radius theorem

Let Ψ be a bounded set of n × n nonnegative matrices in max algebra. In this paper we propose the notions of the max algebra version of the generalized spectral radius μ(Ψ) of Ψ, and the max algebra version of the joint spectral radius η(Ψ) of Ψ. The max algebra version of the generalized spectral radius theorem μ(Ψ) = η(Ψ) is established. We propose the relationship between the generalized spectral radius ρ(Ψ) of Ψ (in the sense of Daubechies and Lagarias) and its max algebra version μ(Ψ). Moreover, a generalization of Elsner and van den Driessche’s lemma is presented as well.     

Exact and approximation algorithms for the min–max k-traveling salesmen problem on a tree

Given k identical salesmen, where k ? 2 is a constant independent of the input size, the min–max k-traveling salesmen problem on a tree is to determine a set of k tours for the salesmen to serve all customers that are located on a tree-shaped network, so that each tour starts from and returns to the root of the tree with the maximum total edge weight of the tours minimized. The problem is known to be NP-hard even when k = 2. In this paper, we have developed a pseudo-polynomial time exact algorithm for this problem with any constant k ? 2, closing a question that has remained open for a decade. Along with this, we have further developed a (1 + ?)-approximation algorithm for any ? > 0.     

The d-precoloring problem for k-degenerate graphs

In this paper we deal with the d-PRECOLORING EXTENSION (d-PREXT) problem in various classes of graphs. The d-PREXT problem is the special case of PRECOLORING EXTENSION problem where, for a fixed constant d, input instances are restricted to contain at most d precolored vertices for every available color. The goal is to decide if there exists an extension of given precoloring using only available colors or to find it.We present a linear time algorithm for both, the decision and the search version of d-PREXT, in the following cases: (i) restricted to the class of k-degenerate graphs (hence also planar graphs) and with sufficiently large set S of available colors, and (ii) restricted to the class of partial k-trees (without any size restriction on S). We also study the following problem related to d-PREXT: given an instance of the d-PREXT problem which is extendable by colors of S, what is the minimum number of colors of S sufficient to use for precolorless vertices over all such extensions? We establish lower and upper bounds on this value for k-degenerate graphs and its various subclasses (e.g., planar graphs, outerplanar graphs) and prove tight results for the class of trees.     

Rudin orthogonality problem on the Bergman space

In this paper, we study the Rudin orthogonality problem on the Bergman space, which is to characterize those functions bounded analytic on the unit disk whose powers form an orthogonal set in the Bergman space of the unit disk. We completely solve the problem if those functions are univalent in the unit disk or analytic in a neighborhood of the closed unit disk. As a consequence, it is shown that an analytic multiplication operator on the Bergman space is unitarily equivalent to a weighted unilateral shift of finite multiplicity n if and only if its symbol is a constant multiple of the n-th power of a Möbius transform, which was obtained via the Hardy space theory of the bidisk in Sun et al. (2008) [10].     

Solving Non-Homogeneous Nested Recursions Using Trees

The solutions to certain nested recursions, such as Conolly’s C(n) = C(n?C(n?1)) + C(n?1?C(n?2)), with initial conditions C(1) = 1, C(2) = 2, have a well-established combinatorial interpretation in terms of counting leaves in an infinite binary tree. This tree-based interpretation, and its generalization to a similar k-term nested recursion, only apply to homogeneous recursions and only solve each recursion for one set of initial conditions determined by the tree. In this paper, we extend the tree-based interpretation to solve a non-homogeneous version of the k-term recursion that includes a constant term. To do so we introduce a tree-grafting methodology that inserts copies of a finite tree into the infinite k-ary tree associated with the solution of the corresponding homogeneous k-term recursion. This technique also solves the given non-homogeneous recursion with various sets of initial conditions.     

An analytical comparison of the LP relaxations of integer models for the k-club problem

Given an undirected graph G = (V, E), a k-club is a subset of nodes that induces a subgraph with diameter at most k. The k-club problem is to find a maximum cardinality k-club. In this study, we use a linear programming relaxation standpoint to compare integer formulations for the k-club problem. The comparisons involve formulations known from the literature and new formulations, built in different variable spaces. For the case k = 3, we propose two enhanced compact formulations. From the LP relaxation standpoint these formulations dominate all other compact formulations in the literature and are equivalent to a formulation with a non-polynomial number of constraints. Also for k = 3, we compare the relative strength of LP relaxations for all formulations examined in the study (new and known from the literature). Based on insights obtained from the comparative study, we devise a strengthened version of a recursive compact formulation in the literature for the k-club problem (k > 1) and show how to modify one of the new formulations for the case k = 3 in order to accommodate additional constraints recently proposed in the literature.