In this paper, we study the uncapacitated facility location problem with service installation costs depending on the type of service required. We propose a polynomial-time approximation algorithm with approximation ra...
详细信息
In this paper, we study the uncapacitated facility location problem with service installation costs depending on the type of service required. We propose a polynomial-time approximation algorithm with approximation ratio 1.808 which improves the previous approximation ratio of 2.391 of Shmoys, Swamy, and Levi. (c) 2007 Elsevier B.V. All rights reserved.
In this work we design an approximation algorithm using neighbors, history and errors (NHE algorithm) to analyze and approximate the behavior of sensors readings after it fails. NHE algorithm computes and associates a...
详细信息
ISBN:
(纸本)9781424429165
In this work we design an approximation algorithm using neighbors, history and errors (NHE algorithm) to analyze and approximate the behavior of sensors readings after it fails. NHE algorithm computes and associates a specific equation to each sensor that has factors computed using neighbors, history data and the approximation error as a feedback factor. In some cases, it is difficult to reach each sensor to read its value either due to a connection problem or the sensor itself is down and not reachable. In those cases, NHE algorithm uses the evaluated equations to approximate this down sensor reading. The results of the experiments using this algorithm prove that it is powerful but with specific constraints.
A clique-transversal set S of a graph G is a subset of vertices intersecting all the cliques of C. where a clique is a complete subgraph maximal under inclusion and having at least two vertices. A clique-independent s...
详细信息
A clique-transversal set S of a graph G is a subset of vertices intersecting all the cliques of C. where a clique is a complete subgraph maximal under inclusion and having at least two vertices. A clique-independent set of the graph G is a set of pairwise disjoint cliques of G. The clique-transversal number tau(C)(G) of G is the cardinality of the smallest clique-transversal set in G and the clique-independence number alpha(C)(G) of G is the cardinality of the largest clique-independent set in G. This paper proves that determining tau(C)(C) and alpha(C)(G) is NP-complete for a cubic planar graph G of girth 3. Further we propose two approximation algorithms for determining tau(C)(G) and alpha(C)(G) in a cubic graph G. (C) 2011 Elsevier B.V. All rights reserved.
Energy efficient multicast problem is one of important issues in ad hoc networks. In this paper, we address the energy efficient multicast problem for discrete power levels in ad hoc wireless networks. The problem of ...
详细信息
Energy efficient multicast problem is one of important issues in ad hoc networks. In this paper, we address the energy efficient multicast problem for discrete power levels in ad hoc wireless networks. The problem of our concern is: given n nodes deployed over 2-D plane and each node v has l(v) transmission power levels and a multicast request (s,D) (clearly, when D is Va-{s}, the multicast request is a broadcast request), how to find a multicast tree rooted at s and spanning all destinations in D such that the total energy cost of the multicast tree is minimized. We first prove that this problem is NP-hard and it is unlikely to have an approximation algorithm with performance ratio rho lnn(rho < 1). Then, we propose a general algorithm for the multicast/broadcast tree problem. And based on the general algorithm, we propose an approximation algorithm and a heuristics for multicast tree problem. Especially, we also propose an efficient heuristic for broadcast tree problem. Simulations ensure our algorithms are efficient.
Given a simple, undirected graph G=(V,E) and a weight function w:E -> a"currency sign(+), we consider the problem of orienting all edges in E so that the maximum weighted outdegree among all vertices is minimi...
详细信息
Given a simple, undirected graph G=(V,E) and a weight function w:E -> a"currency sign(+), we consider the problem of orienting all edges in E so that the maximum weighted outdegree among all vertices is minimized. It has previously been shown that the unweighted version of the problem is solvable in polynomial time while the weighted version is (weakly) NP-hard. In this paper, we strengthen these results as follows: (1) We prove that the weighted version is strongly NP-hard even if all edge weights belong to the set {1,k}, where k is any fixed integer greater than or equal to 2, and that there exists no pseudo-polynomial time approximation algorithm for this problem whose approximation ratio is smaller than (1+1/k) unless P = NP;(2) we present a new polynomial-time algorithm that approximates the general version of the problem within a ratio of (2-1/k), where k is the maximum weight of an edge in G;(3) we show how to approximate the special case in which all edge weights belong to {1,k} within a ratio of 3/2 for k=2 (note that this matches the inapproximability bound above), and (2-2/(k+1)) for any ka parts per thousand yen3, respectively, in polynomial time.
We propose generalizations of a broad class of traditional supply chain planning and logistics models that we call supply chain planning and logistics problems with market choice. Instead of the traditional setting, w...
详细信息
We propose generalizations of a broad class of traditional supply chain planning and logistics models that we call supply chain planning and logistics problems with market choice. Instead of the traditional setting, we are given a set of markets, each specified by a sequence of demands and associated with a revenue. Decisions are made in two stages. In the first stage, one chooses a subset of markets and rejects the others. Once that market choice is made, one needs to construct a minimum-cost production plan (set of facilities) to satisfy all of the demands of all the selected markets. The goal is to minimize the overall lost revenues of rejected markets and the production (facility opening and connection) costs. These models capture important aspects of demand shaping within supply chain planning and logistics models. We introduce a general algorithmic framework that leverages existing approximation results for the traditional models to obtain corresponding results for their counterpart models with market choice. More specifically, any LP-based alpha-approximation for the traditional model can be leveraged to a 1/1-e(-1/alpha)-approximation algorithm for the counterpart model with market choice. Our techniques are also potentially applicable to other covering problems.
In this paper, we study the joint user pairing and resource allocation problem for uplink single carrier frequency-division multiple access (SC-FDMA) system with virtual multiple-input multiple-output (V-MIMO) impleme...
详细信息
ISBN:
(纸本)9781479903085
In this paper, we study the joint user pairing and resource allocation problem for uplink single carrier frequency-division multiple access (SC-FDMA) system with virtual multiple-input multiple-output (V-MIMO) implemented. Different from existing relevant researches, we consider a universal solution based on profit function for this problem instead of studying a particular scheduling policy, and then we explain that it is a MAX SNP-hard problem with high complexity. After that, we will propose a low-complexity heuristic algorithm called First User First (FuF), which is based on the idea of allocating resource to one user first. Moreover, in order to get a more accurate theoretical approximation to this problem, we will propose a constant factor approximation algorithm with polynomial-time complexity using local ratio technique. The simulation results of our algorithms show that the B-LRT algorithm has robust performance compared with other popular algorithms, while the FuF algorithm has lowest computation complexity at the expense of a little performance loss.
作者：
Huang, JunHuang, XiaohongMa, YanBUPT
Inst Networking Technol Beijing 100876 Peoples R China BUPT
Beijing Key Lab Intelligent Telecommun Software & Beijing 100876 Peoples R China
Finding a path that satisfies multiple Quality-of-Service (QoS) constraints is vital to the deployment of current emerged services. However, existing algorithms are not very efficient and effective at finding such a p...
详细信息
Finding a path that satisfies multiple Quality-of-Service (QoS) constraints is vital to the deployment of current emerged services. However, existing algorithms are not very efficient and effective at finding such a path. Moreover, few works focus on three or more QoS constraints. In this paper, we present an enhanced version of fully polynomial time approximation scheme (EFPTAS) for multiconstrainted path optimal (MCOP) problem. Specifically, we make four major contributions. We first allow the proposed algorithm to construct an auxiliary graph, through which the QoS parameters on each of the finding path can be guaranteed not to exceed the given constraints. Then we adopt a concept, called nonlinear definition of path constraints in EFPTAS for reducing both time and space complexity. Also, we enable EFPTAS to run iteratively to facilitate a progressive refinement of the finding result. In addition to these, we identify some "deployment" issues for proposed algorithm, the essential steps that how and when the EFPTAS takes place are presented. By analyzing the proposed algorithm theoretically, we find that the presented EFPTAS can find a (1+epsilon)-approximation path in the network with time complexity O(vertical bar E vertical bar V vertical bar/epsilon) (where vertical bar E vertical bar is the number of edges and vertical bar V vertical bar is the number of nodes), which outperforms the previous best-known algorithm for MCOP. We conduct an extensive comparison between the algorithm presented in this paper and previous best-known study experimentally, our results indicate that EFPTAS can find a path with low complexity and preferable quality. (C) 2011 Elsevier Ltd. All rights reserved.
This paper studies a min-max location-routing problem, which aims to determine both the home depots and the tours for a set of vehicles to service all the customers in a given weighted graph, so that the maximum worki...
详细信息
This paper studies a min-max location-routing problem, which aims to determine both the home depots and the tours for a set of vehicles to service all the customers in a given weighted graph, so that the maximum working time of the vehicles is minimized. The min-max objective is motivated by the needs of balancing or fairness in vehicle routing applications. We have proved that unless NP = P. it is impossible for the problem to have an approximation algorithm that achieves an approximation ratio of less than 4/3. Thus, we have developed the first constant ratio approximation algorithm for the problem. Moreover, we have developed new approximation algorithms for several variants, which improve the existing best approximation ratios in the previous literature. (C) 2011 Elsevier B.V. All rights reserved.
暂无评论