排序方式: 共有88条查询结果,搜索用时 328 毫秒
21.
An improved approximation algorithm for uncapacitated facility location problem with penalties 总被引:1,自引:0,他引:1
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). 相似文献
22.
23.
《Journal of Statistical Computation and Simulation》2012,82(1-2):59-60
We propose two moment ratios based on the first four moments. These moment ratios are useful in identifying different members from a class of discrete or continuous distributions. These ratios are also useful in approximating the Neyman type A and the generalized Poisson distribution by the negative binomial distribution. 相似文献
24.
Christopher A. Sims 《商业与经济统计学杂志》2013,31(1):45-47
Backsolving is a class of methods that generate simulated values for exogenous forcing processes in a stochastic equilibrium model from specified assumed distributions for Euler-equation disturbances. It can be thought of as a way to force the approximation error generated by inexact choice of decision rule or boundary condition into distortions of the distribution of the exogenous shocks in the simulations rather than into violations of the Euler equations as with standard approaches. Here it is applied to a one-sector neoclassical growth model with decision rule generated from a linear-quadratic approximation. 相似文献
25.
《Journal of Statistical Computation and Simulation》2012,82(7):549-564
Consider the logistic linear model, with some explanatory variables overlooked. Those explanatory variables may be quantitative or qualitative. In either case, the resulting true response variable is not a binomial or a beta-binomial but a sum of binomials. Hence, standard computer packages for logistic regression can be inappropriate even if an overdispersion factor is incorporated. Therefore, a discrete exponential family assumption is considered to broaden the class of sampling models. Likelihood and Bayesian analyses are discussed. Bayesian computation techniques such as Laplacian approximations and Markov chain simulations are used to compute posterior densities and moments. Approximate conditional distributions are derived and are shown to be accurate. The Markov chain simulations are performed effectively to calculate posterior moments by using the approximate conditional distributions. The methodology is applied to Keeler's hardness of winter wheat data for checking binomial assumptions and to Matsumura's Accounting exams data for detailed likelihood and Bayesian analyses. 相似文献
26.
Let G=(V,E) be a connected multigraph, whose edges are associated with labels specified by an integer-valued function ℒ:E→ℕ. In addition, each label ℓ∈ℕ has a non-negative cost c(ℓ). The minimum label spanning tree problem (MinLST) asks to find a spanning tree in G that minimizes the overall cost of the labels used by its edges. Equivalently, we aim at finding a minimum cost subset of
labels I⊆ℕ such that the edge set {e∈E:ℒ(e)∈I} forms a connected subgraph spanning all vertices. Similarly, in the minimum label
s
–
t
path problem (MinLP) the goal is to identify an s–t path minimizing the combined cost of its labels. The main contributions of this paper are improved approximation algorithms
and hardness results for MinLST and MinLP. 相似文献
27.
28.
29.
Mohammad Khairul Hasan Hyunwoo Jung Kyung-Yong Chwa 《Journal of Combinatorial Optimization》2008,16(2):155-172
We study Connected Facility Location problems. We are given a connected graph G=(V,E) with nonnegative edge cost c
e
for each edge e∈E, a set of clients D⊆V such that each client j∈D has positive demand d
j
and a set of facilities F⊆V each has nonnegative opening cost f
i
and capacity to serve all client demands. The objective is to open a subset of facilities, say
, to assign each client j∈D to exactly one open facility i(j) and to connect all open facilities by a Steiner tree T such that the cost
is minimized for a given input parameter M≥1. We propose a LP-rounding based 8.29 approximation algorithm which improves the previous bound 8.55 (Swamy and Kumar in
Algorithmica, 40:245–269, 2004). We also consider the problem when opening cost of all facilities are equal. In this case we give a 7.0 approximation algorithm. 相似文献
30.
Hanno Lefmann 《Journal of Combinatorial Optimization》2008,16(2):182-195
In this paper generalizations of Heilbronn’s triangle problem to convex hulls of j points in the unit square [0,1]2 are considered. By using results on the independence number of linear hypergraphs, for fixed integers k≥3 and any integers n≥k a deterministic o(n
6k−4) time algorithm is given, which finds distributions of n points in [0,1]2 such that, simultaneously for j=3,…,k, the areas of the convex hulls determined by any j of these n points are Ω((log n)1/(j−2)/n
(j−1)/(j−2)). 相似文献