PTAS for the minimum weighted dominating set in growth bounded graphs

The minimum weighted dominating set (MWDS) problem is one of the classic NP-hard optimization problems in graph theory with applications in many fields such as wireless communication networks. MWDS in general graphs has been showed not to have polynomial-time constant-approximation if ${\mathcal{NP} \neq \mathcal{P}}$ . Recently, several polynomial-time constant-approximation SCHEMES have been designed for MWDS in unit disk graphs. In this paper, using the local neighborhood-based scheme technique, we present a PTAS for MWDS in polynomial growth bounded graphs with bounded degree constraint.     

Application of the facility location problem to the problem of locating concentrators on an FAA microwave system

The FAA has decided to install, operate, and maintain its own national microwave network called the Radio Communications Link (RCL) network. With this network and its capability to provide concentration points at any one of its microwave repeater locations, the FAA can substantially reduce its leased line budget. This paper addresses the problem of determining the most cost-effective mix of point-to-point leased lines and tail circuits to RCL concentrators for connecting communicating pairs of FAA facilities. The problem, formulated as an integer programming (IP) problem, is shown to be similar to the facility location problem. Also, like the facility problem, integral optimal solutions are frequently obtained. (The reason integral optimal solutions are frequently obtained for the facility location problem is not known.) Thus it is an example, more complex than the facility location problem, where such a phenomenon occurs. Also, the dimensionality of the problem precludes its being solved all in one piece. In this paper we formulate the problem, relate it to the facility location problem, and provide the partitioning and reduction techniques used to solve it in a reasonable amount of time. The partitioning and reduction techniques are independent of any particular formulation for this type of problem, and the solution methodology that would be applied to any subproblem.     

Tabu Search for a Network Loading Problem with Multiple Facilities

This paper examines a network design problem that arises in the telecommunications industry. In this problem, communication between a gateway vertex and a number of demand vertices is achieved through a network of fiber optic cables. Since each cable has an associated capacity (bandwidth), enough capacity must be installed on the links of the network to satisfy the demand, using possibly different types of cables. Starting with a network with no capacity or some capacity already installed, a tabu search heuristic is designed to find a solution that minimizes the cost of installing any additional capacity on the network. This tabu search applies a k-shortest path algorithm to find alternative paths from the gateway to the demand vertices. Numerical results are presented on different types of networks with up to 200 vertices and 100 demand vertices.     

Stochastic Methods for Practical Global Optimization

Engineering design problems often involve global optimization of functions that are supplied as black box functions. These functions may be nonconvex, nondifferentiable and even discontinuous. In addition, the decision variables may be a combination of discrete and continuous variables. The functions are usually computationally expensive, and may involve finite element methods. An engineering example of this type of problem is to minimize the weight of a structure, while limiting strain to be below a certain threshold. This type of global optimization problem is very difficult to solve, yet design engineers must find some solution to their problem – even if it is a suboptimal one. Sometimes the most difficult part of the problem is finding any feasible solution. Stochastic methods, including sequential random search and simulated annealing, are finding many applications to this type of practical global optimization problem. Improving Hit-and-Run (IHR) is a sequential random search method that has been successfully used in several engineering design applications, such as the optimal design of composite structures. A motivation to IHR is discussed as well as several enhancements. The enhancements include allowing both continuous and discrete variables in the problem formulation. This has many practical advantages, because design variables often involve a mixture of continuous and discrete values. IHR and several variations have been applied to the composites design problem. Some of this practical experience is discussed.     

Improved bounds on equilibria solutions in the network design game

In the network design game with n players, every player chooses a path in an edge-weighted graph to connect her pair of terminals, sharing costs of the edges on her path with all other players fairly. It has been shown that the price of stability of any network design game is at most \(H_n\), the n-th harmonic number. This bound is tight for directed graphs.For undirected graphs, it has only recently been shown that the price of stability is at most \(H_n \left( 1-\frac{1}{\Theta (n^4)} \right) \), while the worst-case known example has price of stability around 2.25. We improve the upper bound considerably by showing that the price of stability is at most \(H_{n/2} + \varepsilon \) for any \(\varepsilon \) starting from some suitable \(n \ge n(\varepsilon )\).We also study quality measures of different solution concepts for the multicast network design game on a ring topology. We recall from the literature a lower bound of \(\frac{4}{3}\) and prove a matching upper bound for the price of stability. Therefore, we answer an open question posed by Fanelli et al. (Theor Comput Sci 562:90–100, 2015). We prove an upper bound of 2 for the ratio of the costs of a potential optimizer and of an optimum, provide a construction of a lower bound, and give a computer-assisted argument that it reaches 2 for any precision. We then turn our attention to players arriving one by one and playing myopically their best response. We provide matching lower and upper bounds of 2 for the myopic sequential price of anarchy (achieved for a worst-case order of the arrival of the players). We then initiate the study of myopic sequential price of stability and for the multicast game on the ring we construct a lower bound of \(\frac{4}{3}\), and provide an upper bound of \(\frac{26}{19}\). To the end, we conjecture and argue that the right answer is \(\frac{4}{3}\).     

Location of speed-up subnetworks

Let a network with edge weights, a set of point-to-point transportation requests and a factor \(\alpha \) be given. Our goal is to design a subnetwork of given length along which transportation costs are reduced by \(\alpha \) . This reduces the costs of the network traffic which will choose to use edges of the new subnetwork if this is the more efficient option. Our goal is to design the subnetwork in such a way that the worst-case cost of all routing requests is minimized. The problem occurs in many applications, among others in transportation networks, in backbone, information, communication, or electricity networks. We classify the problem according to the types of the given network and of the network to be established. We are able to clarify the complexity status in all considered cases. It turns out that finding an optimal subtree in a tree already is NP-hard. We therefore further investigate this case and propose results and a solution approach.     

Budget constrained minimum cost connected medians

Several practical instances of network design and location theory problems require the network to satisfy multiple constraints. In this paper, we study a graph-theoretic problem that aims to simultaneously address a network design task and a location-theoretic constraint. The Budget Constrained Connected Median Problem is the following: We are given an undirected graph G=(V,E) with two different edge-weight functions c (modeling the construction or communication cost) and d (modeling the service distance), and a bound B on the total service distance. The goal is to find a subtree T of G with minimum c-cost c(T) subject to the constraint that the sum ∑_vVTdist_d(v,T) of the service distances of all the remaining nodes vVT does not exceed the specified budget B. Here, the service distance dist_d(v,T) denotes the shortest path distance of v to a vertex in T with respect to d. This problem has applications in optical network design and the efficient maintenance of distributed databases.

We formulate this problem as a bicriteria network design problem, and present bicriteria approximation algorithms. We also prove lower bounds on the approximability of the problem which demonstrate that our performance ratios are close to best possible.     

Locating concentrators in centralized computer networks

Topological design of centralized computer communication networks is a complex problem that is generally solved in two phases. The first phase of the design process involves dividing network nodes (terminals or clusters of terminals) into groups, and selecting a concentrator location for each group so that all the nodes in a group are assigned to the same concentrator. The next phase determines topology of links that connect network nodes to concentrators and concentrators to each other and to the central computer. The design problem studied in this paper contains some aspects of both phases. In this problem locations of concentrators, assignments of user nodes to concentrators and the topology of the links connecting concentrators to the central computer are jointly determined. The proposed design method is built around the well known sweep heuristic which is used to partition the node space into sectors. Each of these sectors contain a backbone path connecting concentrators to the central computer.     

A PTAS for minimum connected dominating set in 3-dimensional Wireless sensor networks

When homogeneous sensors are deployed into a three-dimensional space instead of a plane, the mathematical model for the sensor network is a unit ball graph instead of a unit disk graph. It is known that for the minimum connected dominating set in unit disk graph, there is a polynomial time approximation scheme (PTAS). However, that construction cannot be extended to obtain a PTAS for unit ball graph. In this paper, we will introduce a new construction, which gives not only a PTAS for the minimum connected dominating set in unit ball graph, but also improves running time of PTAS for unit disk graph.     

The integrity of a cubic graph

Integrity, a measure of network reliability, is defined as

where G is a graph with vertex set V and m(G−S) denotes the order of the largest component of G−S. We prove an upper bound of the following form on the integrity of any cubic graph with n vertices:

Moreover, there exist an infinite family of connected cubic graphs whose integrity satisfies a linear lower bound I(G)>βn for some constant β. We provide a value for β, but it is likely not best possible. To prove the upper bound we first solve the following extremal problem. What is the least number of vertices in a cubic graph whose removal results in an acyclic graph? The solution (with a few minor exceptions) is that n/3 vertices suffice and this is best possible.     

A Biologically Inspired Optimization Algorithm for Solving Fuzzy Shortest Path Problems with Mixed Fuzzy Arc Lengths

The shortest path problem is among fundamental problems of network optimization. Majority of the optimization algorithms assume that weights of data graph’s edges are pre-determined real numbers. However, in real-world situations, the parameters (costs, capacities, demands, time) are not well defined. The fuzzy set has been widely used as it is very flexible and cost less time when compared with the stochastic approaches. We design a bio-inspired algorithm for computing a shortest path in a network with various types of fuzzy arc lengths by defining a distance function for fuzzy edge weights using \(\alpha \) cuts. We illustrate effectiveness and adaptability of the proposed method with numerical examples, and compare our algorithm with existing approaches.     

GRASP with path-relinking for the generalized quadratic assignment problem

The generalized quadratic assignment problem (GQAP) is a generalization of the NP-hard quadratic assignment problem (QAP) that allows multiple facilities to be assigned to a single location as long as the capacity of the location allows. The GQAP has numerous applications, including facility design, scheduling, and network design. In this paper, we propose several GRASP with path-relinking heuristics for the GQAP using different construction, local search, and path-relinking procedures. We introduce a novel approximate local search scheme, as well as a new variant of path-relinking that deals with infeasibilities. Extensive experiments on a large set of test instances show that the best of the proposed variants is both effective and efficient.     

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.     

Reroute sequence planning in telecommunication networks and compact vector summation

The paper deals with the reroute sequence planning in telecommunication networks. Initially, we are given communication requests between terminal pairs and a path system which is able to satisfy these demands while respecting the physical link capacities. A reconfiguration problem arises when the path set is recalculated by a global optimization method for achieving a better resource utilization. After the recalculation the paths in the routing have to be changed to the optimized ones in the working network. In this case, a sequence of one by one reroutings have to be found with the constraint that the capacities should not be violated and no one of the demands can become unsatisfied during the reroute process. Provided that the (initial and final) free capacities are large enough, such a permutation can be computed. The paper deals with theoretical results giving bounds for these free capacities, with vector-sum and discrepancy methods.     

New algorithms for polynomial and trigonometric interpolation on parallel computers

An interpolation polynomial of orderN is constructed fromp independent subpolynomials of ordern N/p. Each such subpolynomial is found independently and in parallel. Moreover, evaluation of the polynomial at any given point is done independently and in parallel, except for a final step of summation ofp elements. Hence, the algorithm has almost no communication overhead and can be implemented easily on any parallel computer. We give examples of finite-difference interpolation, trigonometric interpolation, and Chebyshev interpolation, and conclude with the general Hermite interpolation problem.     

Tabu search and GRASP for the maximum diversity problem

In this paper, we develop new heuristic procedures for the maximum diversity problem (MDP). This NP-hard problem has a significant number of practical applications such as environmental balance, telecommunication services or genetic engineering. The proposed algorithm is based on the tabu search methodology and incorporates memory structures for both construction and improvement. Although proposed in seminal tabu search papers, memory-based constructions have often been implemented in naïve ways that disregard important elements of the fundamental tabu search proposals. We will compare our tabu search construction with a memory-less design and with previous algorithms recently developed for this problem. The constructive method can be coupled with a local search procedure or a short-term tabu search for improved outcomes. Extensive computational experiments with medium and large instances show that the proposed procedure outperforms the best heuristics reported in the literature within short computational times.     

On-line scheduling on a batch machine to minimize makespan with limited restarts

We study the on-line scheduling on an unbounded batch machine to minimize makespan. In this model, jobs arrive over time and batches are allowed limited restarts. Any batch that contains a job which has already been restarted once cannot be restarted any more. We provide a best possible on-line algorithm for the problem with a competitive ratio .     

Minimum concave-cost network flow problems: Applications,complexity, and algorithms

We discuss a wide range of results for minimum concave-cost network flow problems, including related applications, complexity issues, and solution techniques. Applications from production and inventory planning, and transportation and communication network design are discussed. New complexity results are proved which show that this problem is NP-hard for cases with cost functions other than fixed charge. An overview of solution techniques for this problem is presented, with some new results given regarding the implementation of a particular branch-and-bound approach.     

Designing Least-Cost Nonblocking Broadband Networks

Integrated network technologies, such as ATM, support multimedia applications with vastly different bandwidth needs, connection request rates, and holding patterns. Due to their high level of flexibility and communication rates approaching several gigabits per second, the classical network planning techniques, which rely heavily on statistical analysis, are less relevant to this new generation of networks. In this paper, we propose a new model for broadband networks and investigate the question of their optimal topology from a worst-case performance point of view. Our model is more flexible and realistic than others in the literature, and our worst-case bounds are among the first in this area. Our results include a proof of intractability for some simple versions of the network design problem and efficient approximation algorithms for designing nonblocking networks of provably small cost. More specifically, assuming some mild global traffic constraints, we show that a minimum-cost nonblockingstarnetwork achieves near-optimal cost; the cost ratio is at most 2 if switch source and sink capacities are symmetric and at most 3 when the total source and sink capacities are balanced. In the special case of unit link costs, we can show that a star network is indeed the cheapest nonblocking network.     

Sobolev estimates for constructive uniform-grid FFT interpolatory approximations of spherical functions

The fast Fourier transform (FFT) based matrix-free ansatz interpolatory approximations of periodic functions are fundamental for efficient realization in several applications. In this work we design, analyze, and implement similar constructive interpolatory approximations of spherical functions, using samples of the unknown functions at the poles and at the uniform spherical-polar grid locations \(\left (\frac {j\pi }{N}, \frac {k \pi }{N}\right )\), for j=1,…,N?1, k=0,…,2N?1. The spherical matrix-free interpolation operator range space consists of a selective subspace of two dimensional trigonometric polynomials which are rich enough to contain all spherical polynomials of degree less than N. Using the \({\mathcal {O}}(N^{2})\) data, the spherical interpolatory approximation is efficiently constructed by applying the FFT techniques (in both azimuthal and latitudinal variables) with only \({\mathcal {O}}(N^{2} \log N)\) complexity. We describe the construction details using the FFT operators and provide complete convergence analysis of the interpolatory approximation in the Sobolev space framework that are well suited for quantification of various computer models. We prove that the rate of spectrally accurate convergence of the interpolatory approximations in Sobolev norms (of order zero and one) are similar (up to a log term) to that of the best approximation in the finite dimensional ansatz space. Efficient interpolatory quadratures on the sphere are important for several applications including radiation transport and wave propagation computer models. We use our matrix-free interpolatory approximations to construct robust FFT-based quadrature rules for a wide class of non-, mildly-, and strongly-oscillatory integrands on the sphere. We provide numerical experiments to demonstrate fast evaluation of the algorithm and various theoretical results presented in the article.