Strategyproof mechanisms for 2-facility location games with minimax envy

Journal of Combinatorial Optimization - We study a fairness-based model for 2-facility location games on the real line where the social objective is to minimize the maximum envy over all agents....     

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 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.     

A local search approximation algorithm for a squared metric <Emphasis Type="Italic">k</Emphasis>-facility location problem

We consider a scheduling problem where machines need to be rented from the cloud in order to process jobs. There are two types of machines available which can be rented for machine-type dependent prices and for arbitrary durations. However, a machine-type dependent setup time is required before a machine is available for processing. Jobs arrive online over time, have deadlines and machine-type dependent sizes. The objective is to rent machines and schedule jobs so as to meet all deadlines while minimizing the rental cost. As we observe the slack of jobs to have a fundamental influence on the competitiveness, we parameterize instances by their (minimum) slack. An instance is called to have a slack of \(\beta \) if, for all jobs, the difference between the job’s release time and the latest point in time at which it needs to be started is at least \(\beta \). While for \(\beta < s\) no finite competitiveness is possible, our main result is an online algorithm for \(\beta = (1+\varepsilon )s\) with Open image in new window , where s denotes the largest setup time. Its competitiveness only depends on \(\varepsilon \) and the cost ratio of the machine types and is proven to be optimal up to a factor of Open image in new window .     

A simple greedy approximation algorithm for the minimum connected $$$$-Center problem

In this paper, we consider the connected \(k\)-Center (\(CkC\)) problem, which can be seen as the classic \(k\)-Center problem with the constraint of internal connectedness, i.e., two nodes in a cluster are required to be connected by an internal path in the same cluster. \(CkC\) was first introduced by Ge et al. (ACM Trans Knowl Discov Data 2:7, 2008), in which they showed the \(NP\)-completeness for this problem and claimed a polynomial time approximation algorithm for it. However, the running time of their algorithm might not be polynomial, as one key step of their algorithm involves the computation of an \(NP\)-hard problem. We first present a simple polynomial time greedy-based \(2\)-approximation algorithm for the relaxation of \(CkC\)—the \(CkC^*\). Further, we give a \(6\)-approximation algorithm for \(CkC\).     

An exact algorithm for the maximum probabilistic clique problem

The maximum clique problem is a classical problem in combinatorial optimization that has a broad range of applications in graph-based data mining, social and biological network analysis and a variety of other fields. This article investigates the problem when the edges fail independently with known probabilities. This leads to the maximum probabilistic clique problem, which is to find a subset of vertices of maximum cardinality that forms a clique with probability at least \(\theta \in [0,1]\) , which is a user-specified probability threshold. We show that the probabilistic clique property is hereditary and extend a well-known exact combinatorial algorithm for the maximum clique problem to a sampling-free exact algorithm for the maximum probabilistic clique problem. The performance of the algorithm is benchmarked on a test-bed of DIMACS clique instances and on a randomly generated test-bed.     

An exact algorithm for the multicriteria ordered clustering problem

In the context of multicriteria decision aid, we address the problem of regrouping alternatives into completely ordered categories based on valued preference degrees. We assume that the number of groups is fixed a priori. This will be referred to as the multicriteria ordered clustering problem. The model is based on the definition of an inconsistency matrix and only uses the ordinal properties of the pairwise preference relations. An exact algorithm is proposed to find the ordered partition and is applied as illustration to the Human Development Index.     

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.     

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 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 fast exact algorithm for the problem of optimum cooperation and the structure of its solutions

Given a graph G=(V,E) with edge weights w _e ∈ℝ, the optimum cooperation problem consists in determining a partition of the graph that maximizes the sum of weights of the edges with nodes in the same class plus the number of the classes of the partition. The problem is also known in the literature as the optimum attack problem in networks. Furthermore, a relevant physics application exists.     

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).     

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 simplified algorithm for the all pairs shortest path problem with O(n 2logn) expected time

The best known expected time for the all pairs shortest path problem on a directed graph with non-negative edge costs is O(n ²logn) by Moffat and Takaoka. Let the solution set be the set of vertices to which the given algorithm has so far established shortest paths. The Moffat-Takaoka algorithm maintains complexities before and after the critical point in balance, which is the moment when the size of the solution set is n?n/logn. In this paper, we remove the concept of critical point, whereby we make the algorithm simpler and seamless, resulting in a simpler analysis.     

A Branch and Bound algorithm for general mixed-integer quadratic programs based on quadratic convex relaxation

Let \((MQP)\) be a general mixed-integer quadratic program that consists of minimizing a quadratic function \(f(x) = x^TQx +c^Tx\) subject to linear constraints. Our approach to solve \((MQP)\) is first to consider an equivalent general mixed-integer quadratic problem. This equivalent problem has additional variables \(y_{ij}\) , additional quadratic constraints \(y_{ij}=x_ix_j\) , a convex objective function, and a set of valid inequalities. Contrarily to the reformulation proposed in Billionnet et al. (Math Program 131(1):381–401, 2012), the equivalent problem cannot be directly solved by a standard solver. Here, we propose a new Branch and Bound process based on the relaxation of the non-convex constraints \(y_{ij}=x_ix_j\) to solve \((MQP)\) . Computational experiences are carried out on pure- and mixed-integer quadratic instances. The results show that the solution time of most of the considered instances with up to 60 variables is improved by our Branch and Bound algorithm in comparison with the approach of Billionnet et al. (2012) and with the general mixed-integer nonlinear solver BARON (Sahinidis and Tawarmalani, Global optimization of mixed-integer nonlinear programs, user’s manual, 2010).     

An LP-rounding based algorithm for a capacitated uniform facility location problem with penalties

Journal of Combinatorial Optimization - Facility location problem is a well established research area within Operations Research. Capacitated facility location problem is one of the most important...     

A greedy algorithm for the minimum 2-connected m-fold dominating set problem

To save energy and alleviate interference in a wireless sensor network, connected dominating set (CDS) has been proposed as the virtual backbone. Since nodes may fail due to accidental damage or energy depletion, it is desirable to construct a fault tolerant CDS, which can be modeled as a \(k\)-connected \(m\)-fold dominating set \(((k,m)\)-CDS for short): a subset of nodes \(C\subseteq V(G)\) is a \((k,m)\)-CDS of \(G\) if every node in \(V(G)\setminus C\) is adjacent with at least \(m\) nodes in \(C\) and the subgraph of \(G\) induced by \(C\) is \(k\)-connected.In this paper, we present an approximation algorithm for the minimum \((2,m)\)-CDS problem with \(m\ge 2\). Based on a \((1,m)\)-CDS, the algorithm greedily merges blocks until the connectivity is raised to two. The most difficult problem in the analysis is that the potential function used in the greedy algorithm is not submodular. By proving that an optimal solution has a specific decomposition, we managed to prove that the approximation ratio is \(\alpha +2(1+\ln \alpha )\), where \(\alpha \) is the approximation ratio for the minimum \((1,m)\)-CDS problem. This improves on previous approximation ratios for the minimum \((2,m)\)-CDS problem, both in general graphs and in unit disk graphs.     

A simple approximation algorithm for minimum weight partial connected set cover

Let \(LTQ_n\) be the n-dimensional locally twisted cube. Hsieh and Tu (Theor Comput Sci 410(8–10):926–932, 2009) proposed an algorithm to construct n edge-disjoint spanning trees rooted at a particular vertex 0 in \(LTQ_n\). Later on, Lin et al. (Inf Process Lett 110(10):414–419, 2010) proved that Hsieh and Tu’s spanning trees are indeed independent spanning trees (ISTs for short), i.e., all spanning trees are rooted at the same vertex r and for any other vertex \(v(\ne r)\), the paths from v to r in any two trees are internally vertex-disjoint. Shortly afterwards, Liu et al. (Theor Comput Sci 412(22):2237–2252, 2011) pointed out that \(LTQ_n\) fails to be vertex-transitive for \(n\geqslant 4\) and proposed an algorithm for constructing n ISTs rooted at an arbitrary vertex in \(LTQ_n\). Although this algorithm can simultaneously construct n ISTs, it is hard to be parallelized for the construction of each spanning tree. In this paper, from a modification of Hsieh and Tu’s algorithm, we present a fully parallelized scheme to construct n ISTs rooted at an arbitrary vertex in \(LTQ_n\) in \({\mathcal O}(n)\) time using \(2^n\) vertices of \(LTQ_n\) as processors.     

等待时间受限的置换流水车间调度启发式算法

针对等待时间受限的置换流水车间调度问题,分析了其可行解与流水车间调度最优解的关系,给出了计算最大完工时间的有向图,证明了等待时间受限的置换流水车间调度问题的可逆性,并以此为基础提出了一种启发式算法.算法首先根据等待时间受限约束与无等待(no-wait)约束的相似特征,生成初始工件序列集;然后利用问题可逆性给出了复杂度为O(n2m)的插入优化机制,进一步优化初始解.数据实验的结果验证了启发式算法的可行性和有效性.     

等待时间受限的置换流水车间调度启发式算法

为了繁荣发展哲学社会科学,推动我国学术期刊加强自身建设,提高学术水平,扩大学术影响,全国哲学社会科学规划办公室自2011年启动国家社会科学基金学术期刊资助项目,入选期刊每年资助40万元。2011年和2012年各有100种期刊获得资助,《管理科学》杂志获得国家社会科学基金第二批学术期刊资助。