The r-domination search game on graphs is a game-theoretical approach to the investigation of several graph and hypergraph parameters including treewidth and hypertree width. The task is to identify the minimum number...
详细信息
ISBN:
(纸本)9783642183171
The r-domination search game on graphs is a game-theoretical approach to the investigation of several graph and hypergraph parameters including treewidth and hypertree width. The task is to identify the minimum number of cops sufficient to catch the visible and fast robber. In r-domination search, the robber is being arrested if he resides inside a ball of radius r around some cop. In this setting, the power of the cops does not depend only on how many they are but also on the local topology of the graph around them. This is the main reason why the approximation complexity of the r-domination search game varies considerably, depending on whether r = 0 or r >= 1. We prove that this discrepancy is canceled when the game is played in (non-trivial) graph classes that are closed under taking of minors. We give a constant factor approximation algorithm that for every fixed r and graph H, computes the minimum number of cops required to capture the robber in the r-domination game on graphs excluding H as a minor.
In this paper, we explore two robust models for the k-median and k-means problems: the outlier-version (k-MedO/k-MeaO) and the penalty-version (k-MedP/k-MeaP), enabling the marking and elimination of certain points as...
详细信息
ISBN:
(数字)9789819723409
ISBN:
(纸本)9789819723393;9789819723409
In this paper, we explore two robust models for the k-median and k-means problems: the outlier-version (k-MedO/k-MeaO) and the penalty-version (k-MedP/k-MeaP), enabling the marking and elimination of certain points as outliers. In k-MedO/k-MeaO, the count of outliers is restricted by a specified integer, while in k-MedP/k-MeaP, there's no explicit limit on outlier quantity, yet each outlier incurs a penalty cost. We introduce a novel approach to evaluate the approximation ratio of local search algorithms for these problems. This involves an adapted clustering method that captures pertinent information about outliers within both local and global optimal solutions. For k-MeaP, we enhance the best-known approximation ratio derived from local search, elevating it from 25 + epsilon to 9 + epsilon. The best-known approximation ratio for k-MedP is also obtained. Regarding k-MedO/k-MeaO, only two bi-criteria approximation algorithms based on local search exist. One violates the outlier constraint (limiting outlier count), while the other breaches the cardinality constraint (restricting the number of clusters). We focus on the former algorithm, enhancing its approximation ratios from 17+epsilon to 3+epsilon for k-MedO and from 274 + epsilon to 9 + epsilon for k-MeaO.
The Stable Marriage problem (SM), solved by the famous deferred acceptance algorithm of Gale and Shapley (GS), has many natural generalizations. If we allow ties in preferences, then the problem of finding a maximum s...
详细信息
ISBN:
(纸本)9781611977585
The Stable Marriage problem (SM), solved by the famous deferred acceptance algorithm of Gale and Shapley (GS), has many natural generalizations. If we allow ties in preferences, then the problem of finding a maximum solution becomes NP-hard, and the best known approximation ratio is 1.5 (McDermid ICALP 2009, PaluchWAOA 2011, Z. Kir ' aly MATCH-UP 2012), achievable by running GS on a cleverly constructed modified instance. Another elegant generalization of SM is the matroid kernel problem introduced by Fleiner (IPCO 2001), which is solvable in polynomial time using an abstract matroidal version of GS. Our main result is a simple 1.5-approximation algorithm for the matroid kernel problem with ties. We also show that the algorithm works for several other versions of stability defined for cardinal preferences, by appropriately modifying the instance on which GS is executed. The latter results are new even for the stable marriage setting.
We consider scheduling problems in wireless networks with respect to flexible data rates. That is, more or less data can be transmitted per time depending on the signal quality, which is determined by the signal-to-in...
详细信息
ISBN:
(纸本)9783642330902
We consider scheduling problems in wireless networks with respect to flexible data rates. That is, more or less data can be transmitted per time depending on the signal quality, which is determined by the signal-to-interference-plus-noise ratio (SINR). Each wireless link has a utility function mapping SINR values to the respective data rates. We have to decide which transmissions are performed simultaneously and (depending on the problem variant) also which transmission powers are used. In the capacity-maximization problem, one strives to maximize the overall network throughput, i.e., the summed utility of all links. For arbitrary utility functions (not necessarily continuous ones), we present an O(log n)-approximation when having n communication requests. This algorithm is built on a constant-factor approximation for the special case of the respective problem where utility functions only consist of a single step. In other words, each link has an individual threshold and we aim at maximizing the number of links whose threshold is satisfied. On the way, this improves the result in [Kesselheim, SODA 2011] by not only extending it to individual thresholds but also showing a constant approximation factor independent of assumptions on the underlying metric space or the network parameters. In addition, we consider the latency-minimization problem. Here, each link has a demand, e. g., representing an amount of data. We have to compute a schedule of shortest possible length such that for each link the demand is fulfilled, that is, the overall summed utility (or data transferred) is at least as large as its demand. Based on the capacity-maximization algorithm, we show an O(log(2) n)-approximation for this problem.
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.
Dynamic Voltage Scaling techniques allow the processor to set its speed dynamically in order to reduce energy consumption. It was shown that if the processor can run at arbitrary speeds and uses power s(alpha) when ru...
详细信息
ISBN:
(纸本)9783642106309
Dynamic Voltage Scaling techniques allow the processor to set its speed dynamically in order to reduce energy consumption. It was shown that if the processor can run at arbitrary speeds and uses power s(alpha) when running at speed s, the online heuristic AVR. has a competitive ratio (2 alpha)(alpha)/2. In this paper We first study the online heuristics for the discrete model where the processor can only run at d given speeds. We propose a method to transform online heuristic AVR to an online heuristic for the discrete model and prove a competitive ratio 2(alpha - 1)(alpha - 1)(alpha - 1)(delta(alpha) - 1)(alpha)/(delta - 1)(delta(alpha) - delta)(alpha - 1) + 1, where delta is the maximum ratio between adjacent non-zero speed levels. We also prove that the analysis holds for a class of heuristics that satisfy certain natural properties. We further study the throughput maximization problem when there is an upper bound for the maximum speed. We propose a greedy algorithm with running time O(n(2) log n) and prove that the output schedule is 3-approximation of the throughput and (alpha - 1)(alpha - 1)(3(alpha) - 1)(alpha)/2 alpha(alpha)(3(alpha) (-) (1) - 1)(alpha - 1)-approximation of the energy consumption.
We analyze approximation algorithms for several variants of the traveling salesman problem with multiple objective functions. First, we consider the symmetric TSP (STSP) with gamma-triangle inequality. For this proble...
详细信息
ISBN:
(纸本)9783540695134
We analyze approximation algorithms for several variants of the traveling salesman problem with multiple objective functions. First, we consider the symmetric TSP (STSP) with gamma-triangle inequality. For this problem, we present a deterministic polynomial-time algorithm that achieves an approximation ratio of min{1 + gamma, 2 gamma(2)/2 gamma(2) - 2 gamma+1} + epsilon and a randomized approximation algorithm that achieves a ratio of 2 gamma(3)+2 gamma(2)/3 gamma(2)-2 gamma+1 + epsilon. In particular, we obtain a 2 + e approximation for multi-criteria metric STSP. Then we show that multi-criteria cycle cover problems admit fully polynomial-time randomized approximation schemes. Based on these schemes, we present randomized approximation algorithms for STSP with. - triangle inequality ( ratio 1+gamma/1+3 gamma-4 gamma(2) + epsilon), asymmetric TSP (ATSP) with. - triangle inequality ( ratio 1/2 + gamma(3)/1-3 gamma(2) + epsilon), STSP with weights one and two ( ratio 4/3) and ATSP with weights one and two ( ratio 3/2).
We consider a natural generalization of the knapsack problem and the multiple knapsack problem, which has two phases of packing decisions. In this problem, we have a set of items, several small knapsacks called boxes,...
详细信息
ISBN:
(数字)9783319947761
ISBN:
(纸本)9783319947761;9783319947754
We consider a natural generalization of the knapsack problem and the multiple knapsack problem, which has two phases of packing decisions. In this problem, we have a set of items, several small knapsacks called boxes, and a large knapsack called container. Each item has a size and profit, each box has a size and the container has a capacity. The first phase is to select some items to pack into the boxes, and the second phase is to select the boxes (each includes some packed items) to pack into the container. The total profit of the problem is determined by the items that are selected and packed into the container within some packed box, and the objective is to maximize the total profit. This problem is motivated by various practical applications, e.g., in logistics. It is a generalization of the multiple knapsack problem, and hence is strongly NP-hard. We mainly propose three approximation algorithms for it. Particularly, the first one is a 1/4-approximation algorithm based on its linear programming relaxation;the second one is based on applying the algorithms for the multiple knapsack problem and the knapsack problem, and has an approximation ratio 1/3- epsilon for any small enough epsilon > 0. We finally provide a polynomial time approximation scheme for this problem.
In the Joint Replenishment Problem (JRP), the goal is to coordinate the replenishments of a collection of goods over time so that continuous demands are satisfied with minimum overall ordering and holding costs. We co...
详细信息
ISBN:
(纸本)9783642237195
In the Joint Replenishment Problem (JRP), the goal is to coordinate the replenishments of a collection of goods over time so that continuous demands are satisfied with minimum overall ordering and holding costs. We consider the case when demand rates are constant. Our main contribution is the first hardness result for any variant of JRP with constant demands. When replenishments per commodity are required to be periodic and the time horizon is infinite (which corresponds to the so-called general integer model with correction factor), we show that finding an optimal replenishment policy is at least as hard as integer factorization. This result provides the first theoretical evidence that the JRP with constant demands may have no polynomial-time algorithm and that relaxations and heuristics are called for. We then show that a simple modification of an algorithm by Wildeman et al. (1997) for the JRP gives a fully polynomial-time approximation scheme for the general integer model (without correction factor). We also extend their algorithm to the finite horizon case, achieving an approximation guarantee asymptotically equal to root 9/8.
We consider two closely related fundamental clustering problems in this paper. In the Min-Sum k-Clustering problem, one is given a metric space and has to partition the points into k clusters while minimizing the tota...
详细信息
ISBN:
(数字)9783662476727
ISBN:
(纸本)9783662476727;9783662476710
We consider two closely related fundamental clustering problems in this paper. In the Min-Sum k-Clustering problem, one is given a metric space and has to partition the points into k clusters while minimizing the total pairwise distances between the points assigned to the same cluster. In the Balanced k-Median problem, the instance is the same and one has to obtain a partitioning into k clusters C1, ..., Ck, where each cluster C-i has a center c(i), while minimizing the total assignment costs for the points in the metric;here the cost of assigning a point j to a cluster C-i is equal to vertical bar C-i vertical bar times the distance between j and c(i) in the metric. In this paper, we present an O(log n)-approximation for both these problems where n is the number of points in the metric that are to be served. This is an improvement over the O(epsilon(-1) log(1+epsilon) n)-approximation (for any constant epsilon > 0) obtained by Bartal, Charikar, and Raz [STOC '01]. We also obtain a quasi-PTAS for Balanced k-Median in metrics with constant doubling dimension. As in the work of Bartal et al., our approximation for general metrics uses embeddings into tree metrics. The main technical contribution in this paper is an O(1)-approximation for Balanced k-Median in hierarchically separated trees (HSTs). Our improvement comes from a more direct dynamic programming approach that heavily exploits properties of standard HSTs. In this way, we avoid the reduction to special types of HSTs that were considered by Bartal et al., thereby avoiding an additional O(epsilon(-1) log(epsilon) n) loss.
暂无评论