We consider approval voting elections in which each voter votes for a (possibly empty) set of candidates and the outcome consists of a set of k candidates for some parameter k, e.g., committee elections. We are intere...
详细信息
ISBN:
(纸本)9781577354635
We consider approval voting elections in which each voter votes for a (possibly empty) set of candidates and the outcome consists of a set of k candidates for some parameter k, e.g., committee elections. We are interested in the minimax approval voting rule in which the outcome represents a compromise among the voters, in the sense that the maximum distance between the preference of any voter and the outcome is as small as possible. This voting rule has two main drawbacks. First, computing an outcome thatminimizes the maximum distance is computationally hard. Furthermore, any algorithm that always returns such an outcome provides incentives to voters to misreport their true preferences. In order to circumvent these drawbacks, we consider approximation algorithms, i.e., algorithms that produce an outcome that approximates the minimax distance for any given instance. Such algorithms can be considered as alternative voting rules. We present a polynomial-time 2-approximation algorithm that uses a natural linear programming relaxation for the underlying optimization problem and deterministically rounds the fractional solution in order to compute the outcome;this result improves upon the previously best known algorithm that has an approximation ratio of 3. We are furthermore interested in approximation algorithms that are resistant to manipulation by (coalitions of) voters, i.e., algorithms that do not motivate voters to misreport their true preferences in order to improve their distance from the outcome. We complement previous results in the literature with new upper and lower bounds on strategyproof and group-strategyproof algorithms.
In a classical covering problem, we are given a set of requests that we need to satisfy (fully or partially), by buying a subset of items at minimum cost. For example, in the k-MST problem we want to find the cheapest...
详细信息
ISBN:
(纸本)9783939897347
In a classical covering problem, we are given a set of requests that we need to satisfy (fully or partially), by buying a subset of items at minimum cost. For example, in the k-MST problem we want to find the cheapest tree spanning at least k nodes of an edge-weighted graph. Here, nodes represent requests whereas edges correspond to items. In this paper, we initiate the study of a new family of multi-layer covering problems. Each such problem consists of a collection of h distinct instances of a standard covering problem (layers), with the constraint that all layers share the same set of requests. We identify two main subfamilies of these problems: in an UNION multi-layer problem, a request is satisfied if it is satisfied in at least one layer;in an INTERSECTION multi-layer problem, a request is satisfied if it is satisfied in all layers. To see some natural applications, consider both generalizations of k-MST. UNION k-MST can model a problem where we are asked to connect a set of users to at least one of two communication networks, e.g., a wireless and a wired network. On the other hand, INTERSECTION k-MST can formalize the problem of providing both electricity and water to at least k users.
Given n robots and n target points on the plane, the minimum set cover formation (SCF) problem requires the robots to form a set cover by the minimum number of robots. In previous formation problems by mobile robots, ...
详细信息
ISBN:
(纸本)9783319144726;9783319144719
Given n robots and n target points on the plane, the minimum set cover formation (SCF) problem requires the robots to form a set cover by the minimum number of robots. In previous formation problems by mobile robots, such as gathering and pattern formation, the problems consist only of the mobile robots, and there are no points fixed in the environment. In addition, the problems do not require a control of the number of robots constructing the formation. In this paper, we first introduce the formation problem in which robots move so that they achieve a desired deployment with the minimum number of robots for a given set of positions of fixed points. Since the minimum set cover problem with disks in the centralized settings is NP-hard, our goal is to propose approximation algorithms for the minimum SCF problem. First, we show a minimal SCF algorithm from any initial configuration in the asynchronous system. Moreover, we propose an 8-approximation SCF algorithm in the semi-synchronous system for an initial configuration with a low symmetricity. This approximation algorithm achieves 2(1 + 1/l)(2) approximation ratio for an initial configuration with the lowest symmetricity (l >= 1).
Finding low-cost spanning subgraphs with given degree and connectivity requirements is a fundamental problem in the area of network design. We consider the problem of finding d-regular spanning sub graphs (or d-factor...
详细信息
ISBN:
(纸本)9783319286846;9783319286839
Finding low-cost spanning subgraphs with given degree and connectivity requirements is a fundamental problem in the area of network design. We consider the problem of finding d-regular spanning sub graphs (or d-factors) of minimum weight with connectivity requirements. For the case of k-edge-connectedness, we present approximation algorithms that achieve constant approximation ratios for all d >= 2 . [k/2]. For the case of k-vertex-connectedness, we achieve constant approximation ratios for d >= 2k 1. Our algorithms also work for arbitrary degree sequences if the minimum degree is at least 2 . [k/2] (for k-edge connectivity) or 2k - 1 (for k-vertex-connectivity).
We propose an approximation algorithm based on the Lagrangian or price directive decomposition method to compute an c.-approximate solution of the mixed fractional packing and covering problem: find x is an element of...
详细信息
ISBN:
(纸本)1402081405
We propose an approximation algorithm based on the Lagrangian or price directive decomposition method to compute an c.-approximate solution of the mixed fractional packing and covering problem: find x is an element of B such that f(x) less than or equal to (1 + epsilon)a, g(x) greater than or equal to (1 - epsilon)b where f(x), g(x) are vectors with M nonnegativc convex and concave functions, a and b are M - dimensional nonnegative vectors and B is a convex set that can be queried by an optimization or feasibility oracle. We propose an algorithm that needs only O(Mepsilon(-2) ln(Mepsilon(-1))) iterations or calls to the oracle. The main contribution is that the algorithm solves the general mixed fractional packing and covering problem (in contrast to pure fractional packing and covering problems and to the special mixed packing and covering problem with B = IR+N) and runs in time independent of the so-called width of the problem.
We develop new structural results for apex-minor-free graphs and show their power by developing two new approximation algorithms. The first is an additive approximation for coloring within 2 of the optimal chromatic n...
详细信息
ISBN:
(纸本)9783642029264
We develop new structural results for apex-minor-free graphs and show their power by developing two new approximation algorithms. The first is an additive approximation for coloring within 2 of the optimal chromatic number, which is essentially best possible, and generalizes the seminal result by Thomassen [32] for bounded-genus graphs. This result also improves our understanding from an algorithmic point of view of the venerable Hadwiger conjecture about coloring H-minor-free graphs. The second approximation result is a PTAS for unweighted TSP in apex-minor-free graphs, which generalizes PTASs for TSP in planar graphs and bounded-genus graphs [20,2.24,15]. We strengthen the structural results from the seminal Graph Minor Theory of Robertson and Seymour in the case of apex-minor-free graphs, showing that apices can be made adjacent only to vortices if we generalize the notion of vortices to "quasivortices" of bounded treewidth, proving a conjecture from [10]. We show that this structure theorem is a powerful tool for developing algorithms on apex-minor-free graphs, including for the classic problems of coloring and TSP. In particular, we use this theorem to partition the edges of a graph into k pieces, for any k, such that contracting any piece results in a bounded-treewidth graph, generalizing previous similar results for planar graphs [24] and bounded-genus graphs [15]. We also highlight the difficulties in extending our results to general H-minor-free graphs.
We prove a new structural property regarding the "skyline" of uniform radius disks and use this to derive a number of new sequential and distributed approximation algorithms for well-known optimization probl...
详细信息
ISBN:
(纸本)9783642036842
We prove a new structural property regarding the "skyline" of uniform radius disks and use this to derive a number of new sequential and distributed approximation algorithms for well-known optimization problems oil unit disk graphs (UDGs). Specifically, the paper presents, new approximation algorithms for two problems: domatic partition and 'weighted dominating set (WMDS) on UDGs, both of which are of significant interest to the distributed computing community because of applications to energy conservation in wireless networks. Using the aforementioned skyline property, we derive the first constant-factor approximation algorithm for the domatic partition problem oil UDGs. Prior to our work, the best, approximation factor for this problem was O(log n), obtained by simply using the approximation algorithm for general graphs. From the domatic partition algorithm, we derive a new and simpler constant-factor approximation for WMDS oil UDGs. Because, of "locality" properties that our algorithms possess, both algorithms have, relatively simple constant-round, distributed implementations in the,COCA,C model, where there is no bound on the message size. In addition, we obtain O(log(2) n)-round distributed implementations of these algorithms in the CONGEST model, where message sizes are bounded above by O(log n) bits per message.
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
暂无评论