An improved approximation algorithm for uncapacitated facility location problem with penalties

In this paper, we consider an interesting variant of the classical facility location problem called uncapacitated facility location problem with penalties (UFLWP for short) in which each client is either assigned to an opened facility or rejected by paying a penalty. The UFLWP problem has been effectively used to model the facility location problem with outliers. Three constant approximation algorithms have been obtained (Charikar et al. in Proceedings of the Symposium on Discrete Algorithms, pp. 642–651, 2001; Jain et al. in J. ACM 50(6):795–824, 2003; Xu and Xu in Inf. Process. Lett. 94(3):119–123, 2005), and the best known performance ratio is 2. The only known hardness result is a 1.463-inapproximability result inherited from the uncapacitated facility location problem (Guha and Khuller in J. Algorithms 31(1):228–248, 1999). In this paper, We present a 1.8526-approximation algorithm for the UFLWP problem. Our algorithm significantly reduces the gap between known performance ratio and the inapproximability result. Our algorithm first enhances the primal-dual method for the UFLWP problem (Charikar et al. in Proceedings of the Symposium on Discrete Algorithms, pp. 642–651, 2001) so that outliers can be recognized more efficiently, and then applies a local search heuristic (Charikar and Guha in Proceedings of the 39th IEEE Symposium on Foundations of Computer Science, pp. 378–388, 1999) to further reduce the cost for serving those non-rejected clients. Our algorithm is simple and can be easily implemented. The research of this work was supported in part by NSF through CAREER award CCF-0546509 and grant IIS-0713489. A preliminary version of this paper appeared in the Proceedings of the 11th Annual International Computing and Combinatorics Conference (COCOON’05).     

Approximation algorithm for uniform bounded facility location problem

The uniform bounded facility location problem (UBFLP) seeks for the optimal way of locating facilities to minimize total costs (opening costs plus routing costs), while the maximal routing costs of all clients are at most a given bound M. After building a mixed 0–1 integer programming model for UBFLP, we present the first constant-factor approximation algorithm with an approximation guarantee of 6.853+? for UBFLP on plane, which is composed of the algorithm by Dai and Yu (Theor. Comp. Sci. 410:756–765, 2009) and the schema of Xu and Xu (J. Comb. Optim. 17:424–436, 2008). We also provide a heuristic algorithm based on Benders decomposition to solve UBFLP on general graphes, and the computational experience shows that the heuristic works well.     

An approximation algorithm for the uniform capacitated k-means problem

Journal of Combinatorial Optimization - In this paper, we consider the uniform capacitated k-means problem (UC-k-means), an extension of the classical k-means problem (k-means) in machine learning....     

An approximation algorithm for stochastic multi-level facility location problem with soft capacities

Journal of Combinatorial Optimization - Facility location problem is one of the most important problems in the combinatorial optimization. The multi-level facility location problem and the facility...     

A unified dual-fitting approximation algorithm for the facility location problems with linear/submodular penalties

In this paper, we study two variants of the classical facility location problem, namely, the facility location problem with linear penalties (FLPLP) and the facility location problem with submodular penalties (FLPSP), respectively. We give a unified dual-fitting based approximation algorithm for these two problems, yielding approximation ratios 2 and 3 respectively.     

An approximation algorithm for the <Emphasis Type="Italic">k</Emphasis>-level capacitated facility location problem

We consider the k-level capacitated facility location problem (k-CFLP), which is a natural variant of the classical facility location problem and has applications in supply chain management. We obtain the first (combinatorial) approximation algorithm with a performance factor of \(k+2+\sqrt{k^{2}+2k+5}+\varepsilon\) (ε>0) for this problem.     

On multi-criteria chance-constrained capacitated single-source discrete facility location problems

This work aims at investigating multi-criteria modeling frameworks for discrete stochastic facility location problems with single sourcing. We assume that demand is stochastic and also that a service level is imposed. This situation is modeled using a set of probabilistic constraints. We also consider a minimum throughput at the facilities to justify opening them. We investigate two paradigms in terms of multi-criteria optimization: vectorial optimization and goal programming. Additionally, we discuss the joint use of objective functions that are relevant in the context of some humanitarian logistics problems. We apply the general modeling frameworks proposed to the so-called stochastic shelter site location problem. This is a problem emerging in the context of preventive disaster management. We test the models proposed using two real benchmark data sets. The results show that considering uncertainty and multiple objectives in the type of facility location problems investigated leads to solutions that may better support decision making.     

The facility location problem with Bernoulli demands

This paper presents the facility location problem with Bernoulli demands. In this capacitated discrete location stochastic problem the goal is to define an a priori solution for the locations of the facilities and for the allocation of customers to the operating facilities that minimizes the sum of the fixed costs of the open facilities plus the expected value of the recourse function. The problem is formulated as a two-stage stochastic program and two different recourse actions are considered. For each of them, a closed form is presented for the recourse function and a deterministic equivalent formulation is obtained for the case in which the probability of demand is the same for all customers. Numerical results from computational experiments are presented and analyzed.     

Approximating soft-capacitated facility location problem with uncertainty

In this paper we devise the stochastic and robust approaches to study the soft-capacitated facility location problem with uncertainty. We first present a new stochastic soft-capacitated model called The 2-Stage Soft Capacitated Facility Location Problem and solve it via an approximation algorithm by reducing it to linear-cost version of 2-stage facility location problem and dynamic facility location problem. We then present a novel robust model of soft-capacitated facility location, The Robust Soft Capacitated Facility Location Problem. To solve it, we improve the approximation algorithm proposed by Byrka et al. (LP-rounding algorithms for facility-location problems. CoRR, 2010a) for RFTFL and then treat it similarly as in the stochastic case. The improvement results in an approximation factor of \(\alpha + 4\) for the robust fault-tolerant facility location problem, which is best so far.     

A local search approximation algorithm for the uniform capacitated <Emphasis Type="Italic">k</Emphasis>-facility location problem

In the uniform capacitated k-facility location problem (UC-k-FLP), we are given a set of facilities and a set of clients. Every client has a demand. Every facility have an opening cost and an uniform capacity. For each client–facility pair, there is an unit service cost to serve the client with unit demand by the facility. The total demands served by a facility cannot exceed the uniform capacity. We want to open at most k facilities to serve all the demands of the clients without violating the capacity constraint such that the total opening and serving cost is minimized. The main contribution of this work is to present the first combinatorial bi-criteria approximation algorithm for the UC-k-FLP by violating the cardinality constraint.     

An approximation algorithm for <Emphasis Type="Italic">k</Emphasis>-facility location problem with linear penalties using local search scheme

In this paper, we consider an extension of the classical facility location problem, namely k-facility location problem with linear penalties. In contrast to the classical facility location problem, this problem opens no more than k facilities and pays a penalty cost for any non-served client. We present a local search algorithm for this problem with a similar but more technical analysis due to the extra penalty cost, compared to that in Zhang (Theoretical Computer Science 384:126–135, 2007). We show that the approximation ratio of the local search algorithm is \(2 + 1/p + \sqrt{3+ 2/p+ 1/p^2} + \epsilon \), where \(p \in {\mathbb {Z}}_+\) is a parameter of the algorithm and \(\epsilon >0\) is a positive number.     

A note on the facility location problem with stochastic demands

In this research note that the single source capacitated facility location problem with general stochastic identically distributed demands is studied. The demands considered are independent and identically distributed random variables with arbitrary distribution. The unified a priori solution for the locations of facilities and for the allocation of customers to the operating facilities is found. This solution minimizes the objective function which is the sum of the fixed costs and the value of one of two different recourse functions. For each case the recourse function is given in closed form and a deterministic equivalent formulation of the model is presented. Some numerical examples are also given.     

Approximation algorithm for the parallel-machine scheduling problem with release dates and submodular rejection penalties

In this paper, we consider the parallel-machine scheduling problem with release dates and submodular rejection penalties. In this problem, we are given m identical parallel machines and n jobs. Each job has a processing time and a release date. A job is either rejected, in which case a rejection penalty has to be paid, or accepted and processed on one of the m identical parallel machines. The objective is to minimize the sum of the makespan of the accepted jobs and the rejection penalty of the rejected jobs which is determined by a submodular function. Our main work is to design a 2-approximation algorithm based on the primal-dual framework.

     

The min-p robust optimization approach for facility location problem under uncertainty

Improper value of the parameter p in robust constraints will result in no feasible solutions while applying stochastic p-robustness optimization approach (p-SRO) to solving facility location problems under uncertainty. Aiming at finding the lowest critical p-value of parameter p and corresponding robust optimal solution, we developed a novel robust optimization approach named as min-p robust optimization approach (min-pRO) for P-median problem (PMP) and fixed cost P-median problem (FPMP). Combined with the nearest allocation strategy, the vertex substitution heuristic algorithm is improved and the influencing factors of the lowest critical p-value are analyzed. The effectiveness and performance of the proposed approach are verified by numerical examples. The results show that the fluctuation range of data is positively correlated with the lowest critical p-value with given number of new facilities. However, the number of new facilities has a different impact on lowest critical p-value with the given fluctuation range of data. As the number of new facilities increases, the lowest critical p-value for PMP and FPMP increases and decreases, respectively.

     

A simplified algorithm for the depot location problem

This paper describes a simplified optimization algorithm used for the solution of a classical depot location problem as presented in a Greek Manufacturing Company. Algorithms in the literature for this type of problem are based on the assumption of predetermined fixed costs which are independent of the final size of the depots. This assumption is usually far from reality; the size of each depot does not remain constant during the optimization process and so does the associated fixed cost which is variable with the size of the depot. This assumption is relaxed in the proposed algorithm; the associated fixed cost is modified each time a new customer is allocated to a depot thus changing the required depot size.     

A mixed integer programming and heuristic algorithm for a warehouses location problem

A warehouses location problem is treated using a mixed integer programming and a heuristic algorithm. A simplification of freight rates schedules, based upon shipments consolidation and a linear regression of rates vs distances was made. Warehousing costs were divided according to fixed and variable and related to the throughput of the warehouses. Consideration was given in the analysis to the choice between owning and leasing each warehouse. In the case studied, the analysis demonstrated that a possible saving of approximately 22 per cent in annual distribution costs could be realized under the optimized warehouse location network.     

An hierarchal location—allocation problem

We consider a 2-hierarchal location-allocation problem when p₁ health centers and p₂ hospitals are to be located among n potential locations so as to minimize the total weighted travel distance. We consider the possibility of the referral of θ (0 ≤ θ ≤ 1) proportion of patients from a health center to a hospital. For a graph with certain properties, we extend the notion of a median of a graph to an hierarchal median set. We show how the 2-hierarchal location-allocation problem may be solved as a 2-hierarchal vertex median set problem. We formulate the problem as a mathematical programming problem, suggest five heuristic procedures to solve the problem and report some computational experience. Although we consider the hierarchal location-allocation problem with reference to a health care delivery system, the results of this paper have wide application.     

Strategyproof mechanism design for facility location games with weighted agents on a line

Approximation mechanism design without money was first studied in Procaccia and Tennenholtz (2009) by considering a facility location game. In general, a facility is being opened and the cost of an agent is measured by its distance to the facility. In order to achieve a good social cost, a mechanism selects the location of the facility based on the locations reported by agents. It motivates agents to strategically report their locations to get good outcomes for themselves. A mechanism is called strategyproof if no agents could manipulate to get a better outcome by telling lies regardless of any configuration of other agents. The main contribution in this paper is to explore the strategyproof mechanisms without money when agents are distinguishable. There are two main variations on the nature of agents. One is that agents prefer getting closer to the facility, while the other is that agents prefer being far away from the facility. We first consider the model that directly extends the model in Procaccia and Tennenholtz (2009). In particular, we consider the strategyproof mechanisms without money when agents are weighted. We show that the strategyproof mechanisms in the case of unweighted agents are still the best in the weighted cases. We establish tight lower and upper bounds for approximation ratios on the optimal social utility and the minimum utility when agents prefer to stay close to the facility. We then provide the lower and upper bounds on the optimal social utility and lower bound on the minimum distance per weight when agents prefer to stay far away from the facility. We also extend our study in a natural direction where two facilities must be built on a real line. Secondly, we propose an novel threshold based model to distinguish agents. In this model, we present a strategyproof mechanism that leads to optimal solutions in terms of social cost.     

An approximation algorithm for k-center problem on a convex polygon

This paper studies the constrained version of the k-center location problem. Given a convex polygonal region, every point in the region originates a service demand. Our objective is to place k facilities lying on the region’s boundary, such that every point in that region receives service from its closest facility and the maximum service distance is minimized. This problem is equivalent to covering the polygon by k circles with centers on its boundary which have the smallest possible radius. We present an 1.8841-approximation polynomial time algorithm for this problem.