In the aversion k-clustering problem, given a metric space, we want to cluster the points into k clusters. The cost incurred by each point is the distance to the furthest point in its cluster, and the cost of the clus...
详细信息
ISBN:
(纸本)9783959770132
In the aversion k-clustering problem, given a metric space, we want to cluster the points into k clusters. The cost incurred by each point is the distance to the furthest point in its cluster, and the cost of the clustering is the sum of all these per-point-costs. This problem is motivated by questions in generating automatic abstractions of extensive-form games. We reduce this problem to a "local" k-median problem where each facility has a prescribed radius and can only connect to clients within that radius. Our main results is a constant-factor approximation algorithm for the aversion k-clustering problem via the local k-median problem. We use a primal-dual approach;our technical contribution is a non-local rounding step which we feel is of broader interest.
In many applications, it is a basic operation for the sink to periodically collect reports from all sensors. Since the data gathering process usually proceeds for many rounds, it is important to collect these data eff...
详细信息
In many applications, it is a basic operation for the sink to periodically collect reports from all sensors. Since the data gathering process usually proceeds for many rounds, it is important to collect these data efficiently, that is, to reduce the energy cost of data transmission. Under such applications, a tree is usually adopted as the routing structure to save the computation costs for maintaining the routing tables of sensors. In this paper, we work on the problem of constructing a data aggregation tree that minimizes the total energy cost of data transmission in a wireless sensor network. In addition, we also address such a problem in the wireless sensor network where relay nodes exist and consider the cases where the link quality is not perfect. We show that these problems are NP-complete and propose O(1)-approximation algorithms for each of them. Simulations show that the proposed algorithms have good performance in terms of energy cost.
We consider the One Warehouse Multi-Retailer (OWMR) problem with deterministic time-varying demand in the case where shortages are allowed. Demand may be either backlogged or lost. We present a simple combinatorial al...
详细信息
We consider the One Warehouse Multi-Retailer (OWMR) problem with deterministic time-varying demand in the case where shortages are allowed. Demand may be either backlogged or lost. We present a simple combinatorial algorithm to build an approximate solution from a decomposition of the system into single echelon subproblems. We establish that the algorithm has a performance guarantee of 3 for the OWMR with backlog under mild assumptions on the cost structure. In addition, we improve this guarantee to 2 in the special case of the Joint-Replenishment Problem (JRP) with backlog. As a by-product of our approach, we show that our decomposition provides a new lower bound of the optimal cost. A similar technique also leads to a 2-approximation for the OWMR problem with lost-sales. In all cases, the complexity of the algorithm is linear in the number of retailers and quadratic in the number of time periods, which makes it a valuable tool for practical applications. To the best of our knowledge, these are the first constant approximations for the OWMR with shortages. (C) 2015 Elsevier B.V. and Association of European Operational Research Societies (EURO) within the International Federation of Operational Research Societies (IFORS). All rights reserved.
作者：
Fujii, KaitoKyoto Univ
Grad Sch Informat Sakyo Ku 36-1 Yoshida Honmachi Kyoto 6068501 Japan
Maximizing a monotone submodular function subject to a b-matching constraint is increasing in importance due to its application to the content spread maximization problem, but few practical algorithms are known other ...
详细信息
Maximizing a monotone submodular function subject to a b-matching constraint is increasing in importance due to its application to the content spread maximization problem, but few practical algorithms are known other than the greedy algorithm. The best approximation scheme so far is the local search algorithm, proposed by Feldman, Naor, Schwartz, and Ward [8] (2011). It obtains a 1/(2 + 1/k + is an element of)-approximate solution for an arbitrary positive integer k and positive real number is an element of. For graphs with n vertices and m edges, the running time of the local search algorithm is O(b(k+1) (Delta - 1)(k)nm is an element of(-1)) where Delta is the maximum degree, which is impractical for large problems. In this paper, we present two new algorithms for this problem. One is a find walk algorithm that runs in O(bm) time and achieves 1/4-approximation. It is faster than the greedy algorithm whose approximation ratio is 1/3. The other one is a randomized local search algorithm that is a faster variant of the local search algorithm. In expectation, it runs in O(b(k+1) (Delta - 1)(k-1)m log 1/is an element of) time and obtains a (1/(2 + 1/k) - is an element of)-approximate solution. (C) 2016 Elsevier B.V. All rights reserved.
We describe a half-approximation algorithm, b-SUITOR, for computing a b-MATCHING of maximum weight in a graph with weights on the edges. b-MATCHING is a generalization of the well-known MATCHING problem in graphs, whe...
详细信息
We describe a half-approximation algorithm, b-SUITOR, for computing a b-MATCHING of maximum weight in a graph with weights on the edges. b-MATCHING is a generalization of the well-known MATCHING problem in graphs, where the objective is to choose a subset of M edges in the graph such that at most a specified number b(v) of edges in M are incident on each vertex v. Subject to this restriction we maximize the sum of the weights of the edges in M. We prove that the b-SUITOR algorithm computes the same b-MATCHING as the one obtained by the GREEDY algorithm for the problem. We implement the algorithm on serial and shared-memory parallel processors and compare its performance against a collection of approximation algorithms that have been proposed earlier. Our results show that the b-SUITOR algorithm outperforms the GREEDY and locally dominant edge algorithms by one to two orders of magnitude on a serial processor. The b-SUITOR algorithm has a high degree of concurrency, and it scales well up to 240 threads on a shared-memory multiprocessor. The b-SUITOR algorithm outperforms the locally dominant edge algorithm by a factor of 14 on 16 cores of an Intel Xeon multiprocessor.
Given a graph G with a set of terminals, two weight functions c and d defined on the edge set of G, and a bound D, a popular NP-hard problem in designing networks is to find the minimum cost Steiner tree (under functi...
详细信息
Given a graph G with a set of terminals, two weight functions c and d defined on the edge set of G, and a bound D, a popular NP-hard problem in designing networks is to find the minimum cost Steiner tree (under function c) in G, to connect all terminals in such a way that its diameter (under function d) is bounded by D. Marathe et al. (J. Algoritm. 28(1), 142-171, 1998) proposed an (O(ln n), O(ln n)) approximation algorithm for this bicriteria problem, where n is the number of terminals. The first factor reflects the approximation ratio on the diameter bound D, and the second factor indicates the cost-approximation ratio. Later, Kapoor and Sarwat (Theory Comput. Syst. 41(4), 779-794, 2007) introduced a parameterized approximation algorithm with performance guarantee of (O(p . ln n/ln p), O(ln n/ln p)) for any input value p > 1, by which one can improve the approximation factor for cost at the price of worsening the approximation factor of diameter. In this paper, we consider the reverse scenario in which minimizing the diameter of the solution is more important. We first propose a parameterized approximation algorithm with performance guarantee of (O(ln n/ln p), O(p. H-p . ln n/ln p)), where H-p = 1+ 1/ 2+...+ 1/ p is the pth harmonic number. Parameter p is part of the input and this algorithm runs in polynomial time for constant values of p. We also present another algorithm with approximation ratio of (O(ln n/n p), O(mu . p . ln n/ln p)) which relies on the approximation factor (mu) of the NP-hard problem min-degree constrained minimum spanning tree.
In this paper, we consider the Unsplittable (hard) Capacitated Facility Location Problem (UCFLP) with uniform capacities and present new approximation algorithms for it. This problem is a generalization of the classic...
详细信息
In this paper, we consider the Unsplittable (hard) Capacitated Facility Location Problem (UCFLP) with uniform capacities and present new approximation algorithms for it. This problem is a generalization of the classical facility location problem where each facility can serve at most u units of demand and each client must be served by exactly one facility. This problem is motivated by its applications in many practical problems including supply chain problems of indivisible goods (Verter in Foundations of location analysis, chapter 2. International series in operations research and management science. Springer, Berlin, 2011) and the assignment problem in the content distribution networks (Bateni and Hajiaghayi in Proceedings of the nineteenth annual ACM-SIAM symposium on discrete algorithms, pp 805-814, 2009). While there are several approximation algorithms for the soft capacitated version of this problem (in which one can open multiple copies of each facility) or the splittable version (in which the demand of each client can be divided to be served by multiple open facilities), there are very few results for the UCFLP. It is known that it is NP-hard to approximate this problem within any factor without violating the capacities. So we consider bicriteria -approximations where the algorithm returns a solution whose cost is within factor of the optimum and violates the capacity constraints within factor . Shmoys et al. (Proceedings of the twenty-ninth annual ACM symposium on theory of computing, pp 265-274, 1997) were the first to consider this problem and gave a (9, 4)-approximation. Later results imply (O(1), 2)-approximations, however, no constant factor approximation is known with capacity violation of less than 2. We present a framework for designing bicriteria approximation algorithms for this problem and show two new approximation algorithms with factors (9, 3 / 2) and (29.315, 4 / 3). These are the first algorithms with constant approximation in which the viol
This paper provides a new idea for approximating the inventory cost function to be used in a truncated dynamic program for solving the capacitated lot-sizing problem. The proposed method combines dynamic programming w...
详细信息
This paper provides a new idea for approximating the inventory cost function to be used in a truncated dynamic program for solving the capacitated lot-sizing problem. The proposed method combines dynamic programming with regression, data fitting, and approximation techniques to estimate the inventory cost function at each stage of the dynamic program. The effectiveness of the proposed method is analyzed on various types of the capacitated lot-sizing problem instances with different cost and capacity characteristics. Computational results show that approximation approaches could significantly decrease the computational time required by the dynamic program and the integer program for solving different types of the capacitated lot-sizing problem instances. Furthermore, in most cases, the proposed approximate dynamic programming approaches can accurately capture the optimal solution of the problem with consistent computational performance over different instances.
We present efficient fixed-parameter and approximation algorithms for the NP-hard problem of computing a maximum agreement forest (MAF) of a pair of multifurcating (nonbinary) rooted trees. Multifurcating trees arise ...
详细信息
We present efficient fixed-parameter and approximation algorithms for the NP-hard problem of computing a maximum agreement forest (MAF) of a pair of multifurcating (nonbinary) rooted trees. Multifurcating trees arise naturally as a result of statistical uncertainty in current tree construction methods. The size of an MAF corresponds to the subtree prune-and-regraft distance of the two trees and is intimately connected to their hybridization number. These distance measures are essential tools for understanding reticulate evolution, such as lateral gene transfer, recombination, and hybridization. Our algorithms nearly match the running times of the currently best algorithms for the binary case. This is achieved using a combination of efficient branching rules (similar to but more complex than in the binary case) and a novel edge protection scheme that further reduces the size of the search space the algorithms need to explore.
The bin packing problem is a well-studied problem in combinatorial optimization. In the classical bin packing problem, we are given a list of real numbers in (0, 1] and the goal is to place them in a minimum number of...
详细信息
The bin packing problem is a well-studied problem in combinatorial optimization. In the classical bin packing problem, we are given a list of real numbers in (0, 1] and the goal is to place them in a minimum number of bins so that no bin holds numbers summing to more than 1. The problem is extremely important in practice and finds numerous applications in scheduling, routing and resource allocation problems. Theoretically the problem has rich connections with discrepancy theory, iterative methods, entropy rounding and has led to the development of several algorithmic techniques. In this survey we consider approximation and online algorithms for several classical generalizations of bin packing problem such as geometric bin packing, vector bin packing and various other related problems. There is also a vast literature on mathematical models and exact algorithms for bin packing. However, this survey does not address such exact algorithms. In two-dimensional geometric bin packing, we are given a collection of rectangular items to be packed into a minimum number of unit size square bins. This variant has a lot of applications in cutting stock, vehicle loading, pallet packing, memory allocation and several other logistics and robotics related problems. In d-dimensional vector bin packing, each item is a d-dimensional vector that needs to be packed into unit vector bins. This problem is of great significance in resource constrained scheduling and in recent virtual machine placement in cloud computing. We also consider several other generalizations of bin packing such as geometric knapsack, strip packing and other related problems such as vector scheduling, vector covering etc. We survey algorithms for these problems in offline and online setting, and also mention results for several important special cases. We briefly mention related techniques used in the design and analysis of these algorithms. In the end we conclude with a list of open problems. (C) 2016 Elsevier Inc. A
暂无评论