Multi-dimensional dynamic facility location and fast computation at query points

We present O(nlogn) time algorithms for the minimax rectilinear facility location problem in R¹ and R². The algorithms enable, once they terminate, computing the cost of any given query point in O(logn) time. Based on these algorithms, we develop a preprocessing procedure which enables solving the following two problems: Fast computation of the cost of any query point in Rd, and fast solution for the dynamic location problem in R² (namely, in the presence of an additional facility). Finally, we show that the preprocessing always gives a bound on the optimal value, which allows us in many cases to find the optimum fast (for both the traditional and the dynamic location problems in Rd for any d).     

<Emphasis Type="Italic">k</Emphasis>-Nearest-Neighbor Clustering and Percolation Theory

Let P be a realization of a homogeneous Poisson point process in ℝ ^d with density 1. We prove that there exists a constant k _d , 1<k _d <∞, such that the k-nearest neighborhood graph of P has an infinite connected component with probability 1 when k≥k _d . In particular, we prove that k ₂≤213. Our analysis establishes and exploits a close connection between the k-nearest neighborhood graphs of a Poisson point set and classical percolation theory. We give simulation results which suggest k ₂=3. We also obtain similar results for finite random point sets. Part of the work was done while S.-H. Teng was at Xerox Palo Alto Research Center and MIT. The work of F.F. Yao was supported in part by a grant from the Research Grants Council of the Hong Kong Special Administrative Region, China [Project No. CityU 1165/04E].     

Locating an n-server facility in a stochastic environment

We consider a demand-responsive service system in which n mobile units (servers) are garaged at one facility. Service demands arrive in time as a homogenous Poisson process, but are located over the service region according to an arbitrary probability law. Given a random service demand, either (1) a mobile unit is dispatched to the demand's location to provide on-scene service or (2) the demand is lost (i.e. it is handled by some back-up system). The resultant queueing system is an M/G/n loss system operating in steady state. The objective is to locate the garage facility so that the average cost of response is minimized, where the cost of response is a weighted sum of mean travel time to a random serviced demand and the cost of a lost demand, the weights being the respective probabilities of occurrence. We show that the optimum facility location reduces to Hakimi's well-known minisum location.     

Comparison of genetic programming and radial basis function neural network for open-channel junction velocity field prediction

In this paper, a new fuzzy adaptive artificial physics optimization (FAAPO) algorithm is used to solve security-constrained optimal power flow (SCOPF) problem with wind and thermal power generators. The stochastic nature of wind speed is modeled as a Weibull probability density function. The production cost is modeled with the overestimation and underestimation of available wind energy and included in the conventional SCOPF. Wind generation cost model comprises two components, viz. reserve capacity cost for wind power surplus and penalty cost for wind power shortage. The selection of optimal gravitational constant (G) is a tedious process in conventional artificial physics optimization (APO) method. To overcome this limitation, the gravitational constant (G) is fuzzified in this work. Therefore, based upon the requirement, the gravitational constant changes adaptively. Hence, production cost is reduced, settles at optimum point and takes less number of iterations. The proposed algorithm is tested on IEEE 30-bus system and Indian 75-bus practical system, including wind power in both the test systems. It is observed that FAAPO can outperform BAT algorithm and APO algorithm. Hence, the proposed algorithm can be used for integration of wind power with thermal power generators.

     

Approximation Algorithms for the Class Cover Problem

We introduce the class cover problem, a variant of disk cover with forbidden regions, with applications to classification and facility location problems. We prove similar hardness results to disk cover. We then present a polynomial-time approximation algorithm for class cover that performs within a ln?n+1 factor of optimal, which is nearly tight under standard hardness assumptions. In the special case that the points lie in a d-dimensional space with Euclidean norm, for some fixed constant d, we obtain a polynomial time approximation scheme.     

Minimum-Cost Load-Balancing Partitions

We consider the problem of balancing the load among several service-providing facilities, while keeping the total cost low. Let D be the underlying demand region, and let p ₁,…,p _m be m points representing m facilities. We consider the following problem: Subdivide D into m equal-area regions R ₁,…,R _m , so that region R _i is served by facility p _i , and the average distance between a point q in D and the facility that serves q is minimal. We present constant-factor approximation algorithms for this problem, with the additional requirement that the resulting regions must be convex. As an intermediate result we show how to partition a convex polygon into m equal-area convex subregions so that the fatness of the resulting regions is within a constant factor of the fatness of the original polygon. In fact, we prove that our partition is, up to a constant factor, the best one can get if one’s goal is to maximize the fatness of the least fat subregion. We also discuss the structure of the optimal partition for the aforementioned load balancing problem: indeed, we argue that it is always induced by an additive-weighted Voronoi diagram for an appropriate choice of weights. An earlier version of this paper appeared in the Proceedings of the 22nd Annual ACM Symposium on Computational Geometry, pp. 301–308, 2006. B. Aronov’s research supported in part by NSF grant ITR-0081964 and by a grant from the US-Israel Binational Science Foundation. P. Carmi partially supported by the Lynn and William Frankel Center for Computer Sciences. M.J. Katz partially supported by grant no. 2000160 from the US-Israel Binational Science Foundation.     

Thermohydraulics of square-section microchannels following a serpentine path

Fully developed laminar flow and heat transfer behaviour in serpentine channels with a square cross-section has been studied using computational fluid dynamics. Studies were performed up to Re=200, beyond which the flow became unsteady. The effect of geometric configuration was examined in detail for Re=110, 0.525<R _c/d<2 and 3.6<L/d<12 (where d is the side length of the square section, R _c is radius of curvature of the serpentine bends, and L is the half-wavelength of the serpentine path). Simulations were carried out at (Pr=0.7, 6.13 and 100) constant wall heat flux (H2 boundary condition) and constant wall temperature (T boundary condition). Dean vortices formed at the bends promote fluid mixing transverse to the main flow direction. This leads to significant heat transfer enhancement (up to a factor of 8 at high Pr and Re) with relatively small pressure-drop penalty (factor of 1.8 at high Re). Increasing R _c/d mitigates these effects while the effect of increasing L/d decreases the frictional penalty without greatly affecting the heat transfer enhancement.     

Conchoid surfaces of rational ruled surfaces

The conchoid surface G of a given surface F with respect to a point O is roughly speaking the surface obtained by increasing the radius function of F with respect to O by a constant d. This paper studies real rational ruled surfaces in this context and proves that their conchoid surfaces possess real rational parameterizations, independently of the position of O. Thus any rational ruled surface F admits a rational radius function r(u,v) with respect to any point in space. Besides the general skew ruled surfaces and examples of low algebraic degree we study ruled surfaces generated by rational motions.     

Solvability of systems of polynomial congruences modulo a large prime

We consider the following polynomial congruences problem: given a prime p, and a set of polynomials of total degree at most d, solve the system for solution(s) in . We give a randomized algorithm for the decision version of this problem. For a fixed number of variables, the sequential version of the algorithm has expected time complexity polynomial in d, m and log p; the parallel version has expected time complexity polylogarithmic in d, m and p, using a number of processors, polynomial in d, m and log p. The only point which prevents the algorithm from being deterministic is the lack of a deterministic polynomial time algorithm for factoring univariate polynomials over . Received: April 9, 1997.     

A Modified Fourier–Galerkin Method for the Poisson and Helmholtz Equations

In this paper we present a modified Fourier–Galerkin method for the numerical solution of the Poisson and Helmholtz equations in a d-dimensional box. The inversion of the differential operators requires O(N ^d ) operations, where N ^d is the number of unknowns. The total cost of the presented algorithms is O(N ^d :log₂:N), due to the application of the Fast Fourier Transform (FFT) at the preprocessing stage. The method is based on an extension of the Fourier spaces by adding appropriate functions. Utilizing suitable bilinear forms, approximate projections onto these extended spaces give rapidly converging and highly accurate series expansions.     

Quantum Separation of Local Search and Fixed Point Computation

We give a lower bound of Ω(n ^(d−1)/2) on the quantum query complexity for finding a fixed point of a discrete Brouwer function over grid [n] ^d . Our lower bound is nearly tight, as Grover Search can be used to find a fixed point with O(n ^d/2) quantum queries. Our result establishes a nearly tight bound for the computation of d-dimensional approximate Brouwer fixed points defined by Scarf and by Hirsch, Papadimitriou, and Vavasis. It can be extended to the quantum model for Sperner’s Lemma in any dimensions: The quantum query complexity of finding a panchromatic cell in a Sperner coloring of a triangulation of a d-dimensional simplex with n ^d cells is Ω(n ^(d−1)/2). For d=2, this result improves the bound of Ω(n ^1/4) of Friedl, Ivanyos, Santha, and Verhoeven. More significantly, our result provides a quantum separation of local search and fixed point computation over [n] ^d , for d≥4. Aaronson’s local search algorithm for grid [n] ^d , using Aldous Sampling and Grover Search, makes O(n ^d/3) quantum queries. Thus, the quantum query model over [n] ^d for d≥4 strictly separates these two fundamental search problems.     

Supply facility and input/output point locations in the presence of barriers

This paper studies a facility location model in which two-dimensional Euclidean space represents the layout of a shop floor. The demand is generated by fixed rectangular-shaped user sites and served by a single supply facility. It is assumed that (i) communication between the supply point and a demand facility occurs at an input/output (I/O) point on the demand facility itself, (ii) the facilities themselves pose barriers to travel and (iii) distance measurement is as per the L₁-metric. The objective is to determine optimal locations of the supply facility as well as I/O points on the demand facilities, in order to minimize total transportation costs. Several, increasingly more complex, versions of the model are formulated and polynomial time algorithms are developed to find the optimal locations in each case.Scope and purposeIn a facility layout setting, often a new central supply facility such as a parts supply center or tool crib needs to be located to serve the existing demand facilities (e.g., workstations or maintenance areas). The demand facilities are physical entities that occupy space, that cannot be traveled through, and that receive material from the central facility, through a perimeter I/O (input/output or drop-off/pick-up) point. This paper addresses the joint problem of locating the central facility and determining the I/O point on each demand facility to minimize the total material transportation cost. Different versions of this problem are considered. The solution methods draw from and extend results of location theory for a class of restricted location problems. For practitioners, simple results and polynomial time algorithms are developed for solving these facility (re) design problems.     

随机可满足实例集上警示传播算法的收敛性

信息传播算法在求解随机kSAT问题时有惊人的效果,难解区域变窄.对于这种现象,至今缺少系统的理论解释.警示传播(warning propagation,简称WP)算法是一种基础的信息传播算法,为有效分析WP算法在随机kCNF公式上的收敛性,给出了随机kCNF公式因子图上圈存在的相变点.在随机kCNF公式产生模型G(n,k,p)中,取k=3,p=d/n2,因子图中圈存在的相变点为p=1/8n2.当d＜1/8时,因子图中开始出现圈,且每个连通分支至多有一个圈,因子图中含圈的连通分支的数目以及圈的长度均与n无关.因此,因子图是由森林和一些含有唯一圈的连通分支构成.证明了WP算法在这些实例集上高概率收敛,并且给出了算法的迭代步数为O(logn+s),其中,s为连通分支的大小.     

Implementing Shared Memory on Mesh-Connected Computers and on the Fat-Tree

We present deterministic upper and lower bounds on the slowdown required to simulate an (n, m)-PRAM on a variety of networks. The upper bounds are based on a novel scheme that exploits the splitting and combining of messages. This scheme can be implemented on an n-node d-dimensional mesh (for constant d) and on an n-leaf pruned butterfly and attains the smallest worst-case slowdown to date for such interconnections, namely, O(n^1/d(log(m/n))^1-1/d) for the d-dimensional mesh (with constant d) and O( ) for the pruned butterfly. In fact, the simulation on the pruned butterfly is the first PRAM simulation scheme on an area-universal network. Finally, we prove restricted and unrestricted lower bounds on the slowdown of any deterministic PRAM simulation on an arbitrary network, formulated in terms of the bandwidth properties of the interconnection as expressed by its decomposition tree.     

On the security of Goldreich’s one-way function

Goldreich (ECCC 2000) suggested a simple construction of a candidate one-way function f : {0, 1} ⁿ → {0, 1} ^m where each bit of output is a fixed predicate P of a constant number d of (random) input bits. We investigate the security of this construction in the regime m = Dn, where D(d) is a sufficiently large constant. We prove that for any predicate P that correlates with either one or two of its inputs, f can be inverted with high probability.     

Approximation Algorithms for Access Network Design

Abstract. We consider the problem of designing a minimum cost access network to carry traffic from a set of endnodes to a core network. Trunks are available in K types reflecting economies of scale . A trunk type with a high initial overhead cost has a low cost per unit bandwidth and a trunk type with a low overhead cost has a high cost per unit bandwidth. We formulate the problem as an integer program. We first use a primal—dual approach to obtain a solution whose cost is within O(K ² ) of optimal. Typically the value of K is small. This is the first combinatorial algorithm with an approximation ratio that is polynomial in K and is independent of the network size and the total traffic to be carried. We also explore linear program rounding techniques and prove a better approximation ratio of O(K) . Both bounds are obtained under weak assumptions on the trunk costs. Our primal—dual algorithm is motivated by the work of Jain and Vazirani on facility location [7]. Our rounding algorithm is motivated by the facility location algorithm of Shmoys et al. [12].     

Modeling and controlling flow-induced suspension-head unit vibrations in hard disk drives

 The problem of flow-induced vibrations of suspension-head units (SHUs) in hard disk drives is investigated numerically. Attention is focused on the simplest geometrical and dynamical conditions that retain the physics essential to SHUs in real drives. Conservation equations are solved for the constant property, two-dimensional, unsteady flow of air past a pair of prisms contained in a channel with sliding walls. Each prism simulates the suspension section of a SHU. The prisms face each other symmetrically and are aligned parallel to the sliding channel walls, normal to their direction of motion. The sliding channel walls simulate the rotating disks in a drive. The flow fields obtained are used to calculate SHU vibration frequencies. For this, the suspension section of a SHU is approximated as an Euler–Bernoulli beam (linear motion) of constant h e i g h t2m m w i d t h.2m m h e i g h t.2m m w i d t h5m m h e i g h t2m m w i d t h.2m m-shaped cross-section (henceforth denoted as “U-shaped”) with a point mass, representing the magnetic head, located at its tip. The beam is assumed to be very stiff, meaning that movements near the design point (away from resonances) are small. This allows reliable solutions to be obtained by treating the flow as being unaffected by the miniscule motions of the suspensions, whereas the suspensions are fully affected by the unsteadiness imparted to them by the flow. SHU vibration characteristics have been determined relative to the flow fields that induce them for a variety of conditions. The paper discusses a subset of these for a flow at 50 m/s as well as the possible adaptation of interactive computational-experimental methodologies (ICEME) to minimize and/or control flow-induced vibrations of SHUs in hard drives. Received: 28 August 2001/Accepted: 17 December 2001