We present an (e(O(p)) log l/log log l)-approximation algorithm for socially fair clustering with the l(p)-objective. In this problem, we are given a set of points in a metric space. Each point belongs to one (or seve...
详细信息
We present an (e(O(p)) log l/log log l)-approximation algorithm for socially fair clustering with the l(p)-objective. In this problem, we are given a set of points in a metric space. Each point belongs to one (or several) of l groups. The goal is to find a k-medians, k-means, or, more generally, l-clustering that is simultaneously good for all of the groups. More precisely, we need to find a set of k centers C so as to minimize the maximum over all groups j of Sigma (u in group j) (d(u;C)p). The socially fair clustering problem was independently proposed by Abbasi, Bhaskara, and Venkatasubramanian (2021) and Ghadiri, Samadi, and Vempala (2021). Our algorithm improves and generalizes their O (l)-approximation algorithms for the problem. The natural LP relaxation for the problem has an integrality gap of Omega(l). In order to obtain our result, we introduce a strengthened LP relaxation and show that it has an integrality gap of Theta( log l/log log l) for a fixed p. Additionally, we present a bicriteria approximation algorithm, which generalizes the bicriteria approximation of Abbasi et al. (2021).
We are given a set of items, and a set of knapsacks. Both the weight and the profit of an item are functions of the knapsack, and each knapsack has a positive real capacity. A restriction is setting that the number of...
详细信息
ISBN:
(纸本)9781479986460
We are given a set of items, and a set of knapsacks. Both the weight and the profit of an item are functions of the knapsack, and each knapsack has a positive real capacity. A restriction is setting that the number of the items which are admissible to each knapsack is no more than k, and these items are taken as input for each knapsack. We consider two following objectives: (1) maximizing the total profit of all the knapsacks (Max-Sum k-GMK);(2) maximizing the minimum profit of all the knapsacks (Max-Min k-GMK). We show that the two problems are NP-complete when k is greater than or equal t to 4. For the Max-Sum k-GMK problem, we can obtain a 1/2-approximation algorithm, and especially when k=2, we design an optimal algorithm. For the Max-Min k-GMK problem, we present a 1/(k-1)-approximation algorithm, and especially when k=2, this algorithm is an optimal algorithm.
We study the approximability of two related problems on graphs with n nodes and m edges: n-Pairs Shortest Paths (n-PSP), where the goal is to find a shortest path between O(n) prespecified pairs, and All Node Shortest...
详细信息
ISBN:
(纸本)9781665455190
We study the approximability of two related problems on graphs with n nodes and m edges: n-Pairs Shortest Paths (n-PSP), where the goal is to find a shortest path between O(n) prespecified pairs, and All Node Shortest Cycles (ANSC), where the goal is to find the shortest cycle passing through each node. Approximate n-PSP has been previously studied, mostly in the context of distance oracles. We ask the question of whether approximate n-PSP can be solved faster than by using distance oracles or All Pair Shortest Paths (APSP). ANSC has also been studied previously, but only in terms of exact algorithms, rather than approximation. We provide a thorough study of the approximability of n-PSP and ANSC, providing a wide array of algorithms and conditional lower bounds that trade off between running time and approximation ratio. A highlight of our conditional lower bounds results is that for any integer k >= 1, under the combinatorial 4k-clique hypothesis, there is no combinatorial algorithm for unweighted undirected n-PSP with approximation ratio better than 1 + 1/k that runs in O(m(2-2/(k+1)) n(1/(k+1)-epsilon)) time. This nearly matches an upper bound implied by the result of Agarwal (2014). Our algorithms use a surprisingly wide range of techniques, including techniques from the girth problem, distance oracles, approximate APSP, spanners, fault-tolerant spanners, and link-cut trees. A highlight of our algorithmic results is that one can solve both n-PSP and ANSC in (O) over tilde (m + n(3/2+epsilon)) time1 with approximation factor 2 + epsilon (and additive error that is function of epsilon), for any constant epsilon > 0. For n-PSP, our conditional lower bounds imply that this approximation ratio is nearly optimal for any subquadratic-time combinatorial algorithm. We further extend these algorithms for n-PSP and ANSC to obtain a time/accuracy trade-off that includes near-linear time algorithms. Additionally, for ANSC, for all integers k >= 1, we extend the very recent a
Relay nodes are introduced to the next generation cellular networks to enhance coverage and improve system capacity, leading to a new radio network planning paradigm. In this paper, we study two planning problems for ...
详细信息
ISBN:
(纸本)9781467359399;9781467359382
Relay nodes are introduced to the next generation cellular networks to enhance coverage and improve system capacity, leading to a new radio network planning paradigm. In this paper, we study two planning problems for cellular networks with relay nodes: Minimum cost cell planning and budgeted cell planning. The former is to minimize the total installation cost for opening base stations (BSs), including macro BSs and relay nodes, while satisfying all users' traffic demands. The latter is to maximize the number of users with predefined traffic demands under a given budget. Both of the problems are NP-hard. We present approximation algorithms to work out promising solutions to these problems. For the minimum cost cell planning, we develop an O(log W)-approximation algorithm, where W is the maximum capacity of macro BSs. For the budgeted cell planning, we prove that the problem is NP-hard to approximate and give an e-1/3e-1-approximation algorithm for a special case of the problem, which is general enough to meet practical requirements.
We consider the following taxonomy labeling problem. Each node of an n-node tree has to be labeled with the values of kappa attributes. A partial labeling is given as part of the input. The goal is to complete this la...
详细信息
ISBN:
(纸本)9780898716474
We consider the following taxonomy labeling problem. Each node of an n-node tree has to be labeled with the values of kappa attributes. A partial labeling is given as part of the input. The goal is to complete this labeling, minimizing the maximum variation in labeling along an edge. A special case of this problem (which we call the label extension problem), where every node is either completely labeled or not labeled at all, has been considered previously. We present an O(log(2) kappa)-approximation algorithm based on a natural linear programming relaxation. Our results reduce the taxonomy labeling problem to another problem we introduce, called the multicut packing problem (on trees): given kappa multicommodity flow instances, find a multicut for each instance so as to minimize the maximum number of multicuts that, use any single edge. Our algorithm yields an O(log(2) kappa)-approximation algorithm for this more general problem. We show that;the integrality gap of our relaxation is Omega(log kappa), even when applied to the taxonomy labeling problem with 0-1 labels. For the label extension problem, we considerably improve the previous O(log n) approximation guarantee and give the first constant-factor approximation algorithm for this problem. Our work relies on relating the label extension problem to questions on Lipschitz extensions of functions into Banach spaces. In particular, our approximation algorithm builds upon Matousek's tree metrics extension theorem. Our algorithm also works for other metrics on the label-set, such as edit distance with unit-cost operations, and more generally any shortest path metric induced by an unweighted graph.
In this paper we study a team orienteering problem, which is to find service paths for multiple vehicles in a network such that the profit sum of serving the nodes in the paths is maximized, subject to the cost budget...
详细信息
ISBN:
(纸本)9781728164120
In this paper we study a team orienteering problem, which is to find service paths for multiple vehicles in a network such that the profit sum of serving the nodes in the paths is maximized, subject to the cost budget of each vehicle. This problem has many potential applications in IoT and smart cities, such as dispatching energy-constrained mobile chargers to charge as many energy-critical sensors as possible to prolong the network lifetime. In this paper, we first formulate the team orienteering problem, where different vehicles are different types, each node can be served by multiple vehicles, and the profit of serving the node is a submodular function of the number of vehicles serving it. We then propose a novel (1 - (1/e)1/2+epsilon)-approximation algorithm for the problem, where epsilon is a given constant with 0 < epsilon <= 1 and e is the base of the natural logarithm. In particular, the approximation ratio is no less than 0.32 when epsilon = 0.5. In addition, for a special team orienteering problem with the same type of vehicles and the profits of serving a node once and multiple times being the same, we devise an improved approximation algorithm. Finally, we evaluate the proposed algorithms with simulation experiments, and the results of which are very promising. Precisely, the profit sums delivered by the proposed algorithms are approximately 12.5% to 17.5% higher than those by existing algorithms.
Consider the following online version of the submodular maximization problem under a matroid constraint. We are given a set of elements over which a matroid is defined. The goal is to incrementally choose a subset tha...
详细信息
ISBN:
(纸本)9783642315947
Consider the following online version of the submodular maximization problem under a matroid constraint. We are given a set of elements over which a matroid is defined. The goal is to incrementally choose a subset that remains independent in the matroid over time. At each time, a new weighted rank function of a different matroid (one per time) over the same elements is presented;the algorithm can add a few elements to the incrementally constructed set, and reaps a reward equal to the value of the new weighted rank function on the current set. The goal of the algorithm as it builds this independent set online is to maximize the sum of these (weighted rank) rewards. As in regular online analysis, we compare the rewards of our online algorithm to that of an offline optimum, namely a single independent set of the matroid that maximizes the sum of the weighted rank rewards that arrive over time. This problem is a natural extension of two well-studied streams of earlier work: the first is on online set cover algorithms (in particular for the max coverage version) while the second is on approximately maximizing submodular functions under a matroid constraint. In this paper, we present the first randomized online algorithms for this problem with poly-logarithmic competitive ratio. To do this, we employ the LP formulation of a scaled reward version of the problem. Then we extend a weighted-majority type update rule along with uncrossing properties of tight sets in the matroid polytope to find an approximately optimal fractional LP solution. We use the fractional solution values as probabilities for a online randomized rounding algorithm. To show that our rounding produces a sufficiently large reward independent set, we prove and use new covering properties for randomly rounded fractional solutions in the matroid polytope that may be of independent interest.
Multicommodity flow (MF) problems have a wide variety of applications in areas such as VLSI circuit design, network design, etc., and are therefore very well studied. The fractional MF problems are polynomial time sol...
详细信息
ISBN:
(纸本)9781424402212
Multicommodity flow (MF) problems have a wide variety of applications in areas such as VLSI circuit design, network design, etc., and are therefore very well studied. The fractional MF problems are polynomial time solvable while integer versions are NP-complete. However, exact algorithms to solve the fractional MF problems have high computational complexity. Therefore approximation algorithms to solve the fractional MF problems have been explored in the literature to reduce their computational complexity. Using these approximation algorithms and the randomized rounding technique, polynomial time approximation algorithms have been explored in the literature. In the design of high-speed networks, such as optical wavelength division multiplexing (WDM) networks, providing survivability carries great significance. Survivability is the ability of the network to recover from failures. It further increases the complexity of network design and presents network designers with more formidable challenges. In this work we formulate the survivable versions of the MF problems. We build approximation algorithms for the survivable multicommodity How (SMF) problems based on the framework of the approximation algorithms for the MF problems presented in [1] and [2]. We discuss applications of the SMF problems to solve survivable routing in capacitated networks.
作者：
Tan, XHTokai Univ
Sch High Technol Human Welfare Numazu 4100395 Japan
Given a simple polygon P with n vertices and a starting point s on its boundary, the watchman route problem asks for a shortest route in P through s such that each point in the interior of the polygon can be seen from...
详细信息
Given a simple polygon P with n vertices and a starting point s on its boundary, the watchman route problem asks for a shortest route in P through s such that each point in the interior of the polygon can be seen from at least one point along the route. In this paper, we present a simple, linear-time algorithm for computing a watchman route of length at most root2 times that of the shortest watchman route. The best known algorithm for computing the shortest watchman route through s takes 0(n 4) time. In addition, it is too complicated to be suitable in practice. Moreover, our approximation scheme can be applied to the zookeeper's problem, which is a variant of the watchman route problem. (C) 2003 Published by Elsevier B.V.
In this paper, we consider the restless bandit problem, which is one of the most well-studied generalizations of the celebrated stochastic multi-armed bandit problem in decision theory. In its ultimate generality, the...
详细信息
ISBN:
(纸本)9780898716801
In this paper, we consider the restless bandit problem, which is one of the most well-studied generalizations of the celebrated stochastic multi-armed bandit problem in decision theory. In its ultimate generality, the restless bandit problem is known to be PSPACE-Hard to approximate to any non-trivial factor, and little progress has been made on this problem despite its significance in modeling activity allocation under uncertainty. We make progress on this problem by showing that for an interesting and general subclass that we term MONOTONE bandits, a surprisingly simple and intuitive greedy policy yields a factor 2 approximation. Such greedy policies are termed index policies, and are popular due to their simplicity and their optimality for the stochastic multi-armed bandit problem. The MONOTONE bandit problem strictly generalizes the stochastic multi-armed bandit problem, and naturally models multi-project scheduling where the state of a project becomes increasingly uncertain when the project is not scheduled. We develop several novel techniques in the design and analysis of the index policy. Our algorithm proceeds by introducing a novel "balance" constraint to the dual of a well-known LP relaxation to the restless bandit problem. This is followed by a structural characterization of the optimal solution by using both the exact primal as well as dual complementary slackness conditions. This yields an interpretation of the dual variables as potential functions from which we derive the index policy and the associated analysis.
暂无评论