Approval-based multiwinner voting rules have recently received much attention in the Computational Social Choice literature. Such rules aggregate approval ballots and determine a winning committee of alternatives. To assess effectiveness, we propose to employ new noise models that are specifically tailored for approval votes and committees. These models take as input a ground truth committee and return random approval votes to be thought of as noisy estimates of the ground truth. A minimum robustness requirement for an approval-based multiwinner voting rule is to return the ground truth when applied to profiles with sufficiently many noisy votes. Our results indicate that approval-based multiwinner voting can indeed be robust to reasonable noise. We further refine this finding by presenting a hierarchy of rules in terms of how robust to noise they are.

International audience

In 1876, Charles Lutwidge Dodgson suggested the intriguing voting rule that today bears his name. Although Dodgson’s rule is one of the most well-studied voting rules, it suffers from serious deficiencies, both from the computational point of view—it is NP-hard even to approximate the Dodgson score within sublogarithmic factors—and from the social choice point of view—it fails basic social choice desiderata such as monotonicity and homogeneity. However, this does not preclude the existence of approximation algorithms for Dodgson that are monotonic or homogeneous, and indeed it is natural to ask whether such algorithms exist. In this article, we give definitive answers to these questions. We design a monotonic exponential-time algorithm that yields a 2-approximation to the Dodgson score, while matching this result with a tight lower bound. We also present a monotonic polynomial-time O(log m )-approximation algorithm (where m is the number of alternatives); this result is tight as well due to a complexity-theoretic lower bound. Furthermore, we show that a slight variation on a known voting rule yields a monotonic, homogeneous, polynomial-time O( m log m )-approximation algorithm and establish that it is impossible to achieve a better approximation ratio even if one just asks for homogeneity. We complete the picture by studying several additional social choice properties; for these properties, we prove that algorithms with an approximation ratio that depends only on m do not exist.

Sponsored search auctions are the main source of revenue for search engines. In such an auction, a set of utility maximizing advertisers competes for a set of ad slots. The assignment of advertisers to slots depends on the bids they submit; these bids may be different than the true valuations of the advertisers for the slots. Variants of the celebrated VCG auction mechanism guarantee that advertisers act truthfully and, under some assumptions, lead to revenue or social welfare maximization. Still, the sponsored search industry mostly uses generalized second price (GSP) auctions; these auctions are known to be nontruthful and suboptimal in terms of social welfare and revenue. In an attempt to explain this tradition, we study a Bayesian setting wherein the valuations of advertisers are drawn independently from a common regular probability distribution. In this setting, it is well known from the work of Myerson [1981] that the optimal revenue is obtained by the VCG mechanism with a particular reserve price that depends on the probability distribution. We show that, by appropriately setting the reserve price, the revenue over any Bayes-Nash equilibrium of the game induced by the GSP auction is at most a small constant factor away from the optimal revenue, improving previous results of Lucier et al. [2012]. Our analysis is based on the Bayes-Nash equilibrium conditions and the improved results are obtained by bounding the utility of each player at equilibrium using infinitely many deviating bids and also by developing novel prophet-like inequalities.

In sponsored search auctions, advertisers compete for a number of available advertisement slots of different quality. The auctioneer decides the allocation of advertisers to slots using bids provided by them. Since the advertisers may act strategically and submit their bids in order to maximize their individual objectives, such an auction naturally defines a strategic game among the advertisers. In order to quantify the efficiency of outcomes in generalized second price auctions, we study the corresponding games and present new bounds on their price of anarchy, improving the recent results of Paes Leme and Tardos [16] and Lucier and Paes Leme [13]. For the full information setting, we prove a surprisingly low upper bound of 1.282 on the price of anarchy over pure Nash equilibria. Given the existing lower bounds, this bound denotes that the number of advertisers has almost no impact on the price of anarchy. The proof exploits the equilibrium conditions developed in [16] and follows by a detailed reasoning about the structure of equilibria and a novel relation of the price of anarchy to the objective value of a compact mathematical program. For more general equilibrium classes (i.e., mixed Nash, correlated, and coarse correlated equilibria), we present an upper bound of 2.310 on the price of anarchy. We also consider the setting where advertisers have incomplete information about their competitors and prove a price of anarchy upper bound of 3.037 over Bayes-Nash equilibria. In order to obtain the last two bounds, we adapt techniques of Lucier and Paes Leme [13] and significantly extend them with new arguments.

In 1876 Charles Lutwidge Dodgson suggested the intriguing voting rule that today bears his name. Although Dodgson's rule is one of the most well-studied voting rules, it suffers from serious deficiencies, both from the computational point of view - it is NP-hard even to approximate the Dodgson score within sublogarithmic factors - and from the social choice point of view - it fails basic social choice desiderata such as monotonicity and homogeneity.

We study congestion games where players aim to access a set of resources. Each player has a set of possible strategies and each resource has a function associating the latency it incurs to the players using it. Players are non--cooperative and each wishes to follow a strategy that minimizes her own latency with no regard to the global optimum. Previous work has studied the impact of this selfish behavior on system performance. In this article, we study the question of how much the performance can be improved if players are forced to pay taxes for using resources. Our objective is to extend the original game so that selfish behavior does not deteriorate performance. We consider atomic congestion games with linear latency functions and present both negative and positive results. Our negative results show that optimal system performance cannot be achieved even in very simple games. On the positive side, we show that there are ways to assign taxes that can improve the performance of linear congestion games by forcing players to follow strategies where the total latency suffered is within a factor of 2 of the minimum possible; this result is shown to be tight. Furthermore, even in cases where in the absence of taxes the system behavior may be very poor, we show that the total disutility of players (latency plus taxes) is not much larger than the optimal total latency. Besides existential results, we show how to compute taxes in time polynomial in the size of the game by solving convex quadratic programs. Similar questions have been extensively studied in the model of non-atomic congestion games. To the best of our knowledge, this is the first study of the efficiency of taxes in atomic congestion games.

The voting rules proposed by Dodgson and Young are both designed to find the alternative closest to being a Condorcet winner, according to two different notions of proximity; the score of a given alternative is known to be hard to compute under either rule. In this paper, we put forward two algorithms for approximating the Dodgson score: an LP-based randomized rounding algorithm and a deterministic greedy algorithm, both of which yield an approximation ratio, where m is the number of alternatives; we observe that this result is asymptotically optimal, and further prove that our greedy algorithm is optimal up to a factor of 2, unless problems in have quasi-polynomial time algorithms. Although the greedy algorithm is computationally superior, we argue that the randomized rounding algorithm has an advantage from a social choice point of view. Further, we demonstrate that computing any reasonable approximation of the ranking produced by Dodgson's rule is -hard. This result provides a complexity-theoretic explanation of sharp discrepancies that have been observed in the Social Choice Theory literature when comparing Dodgson elections with simpler voting rules. Finally, we show that the problem of calculating the Young score is -hard to approximate by any factor. This leads to an inapproximability result for the Young ranking.

We study the problem of maintaining connectivity in a wireless network where the network nodes are equipped with directional antennas. Nodes correspond to points on the plane and each uses a directional antenna modeled by a sector with a given angle and radius. The connectivity problem is to decide whether or not it is possible to orient the antennas so that the directed graph induced by the node transmissions is strongly connected. We present algorithms for simple polynomial-time-solvable cases of the problem, show that the problem is NP-complete in the $2$-dimensional case when the sector angle is small, and present algorithms that approximate the minimum radius to achieve connectivity for sectors with a given angle. We also discuss several extensions to related problems. To the best of our knowledge, the problem has not been studied before in the literature.

Abstract We address an important communication issue arising in wireless cellular networks that utilize frequency division multiplexing (FDM) technology. In such networks, many users within the same geographical region (cell) can communicate simultaneously with other users of the network using distinct frequencies. The spectrum of the available frequencies is limited; thus, efficient solutions to the call control problem are essential. The objective of the call control problem is, given a spectrum of available frequencies and users that wish to communicate, to maximize the benefit, i.e., the number of users that communicate without signal interference. We consider cellular networks of reuse distance k ≥ 2 and we study the online version of the problem using competitive analysis. In cellular networks of reuse distance 2, the previously best known algorithm that beats the lower bound of 3 on the competitiveness of deterministic algorithms, works on networks with one frequency, achieves a competitive ratio against oblivious adversaries, which is between 2.469 and 2.651, and uses a number of random bits at least proportional to the size of the network. We significantly improve this result by presenting a series of simple randomized algorithms that have competitive ratios significantly smaller than 3, work on networks with arbitrarily many frequencies, and use only a constant number of random bits or a comparable weak random source. The best competitiveness upper bound we obtain is 16/7 using only four random bits. In cellular networks of reuse distance k> 2, we present simple randomized online call control algorithms with competitive ratios, which significantly beat the lower bounds on the competitiveness of deterministic ones and use only O(log k) random bits. Also, we show new lower bounds on the competitiveness of online call control algorithms in cellular networks of any reuse distance. In particular, we show that no online algorithm can achieve competitive ratio better than 2, 25/12, and 2.5, in cellular networks with reuse distance k ε {2, 3, 4}, k = 5, and k ≥ 6, respectively. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008

In this paper we address an important communication issue arising in cellular (mobile) networks that utilize Frequency Division Multiplexing (FDM) technology. In such networks, many users within the same geographical region can communicate simultaneously with other users of the network using distinct frequencies. The spectrum of the available frequencies is limited; thus, efficient solutions to the call control problem are essential. The objective of the call control problem is, given a spectrum of available frequencies and users that wish to communicate, to maximize the number of users that communicate without signal interference. Using competitive analysis, we study the performance of algorithm p-RANDOM; an intuitive on-line randomized call control algorithm proposed previously for cellular networks. We give upper and lower bounds of its competitive ratio against oblivious adversaries as a function of the parameter p. Optimizing the upper bound function, we prove that there exists a 2.651-competitive randomized call control algorithm. In this way, we significantly improve the best known upper bound on the competitiveness of on-line randomized call control which was 2.934.

We study the problem of allocating optical bandwidth to sets of communication requests in all–optical networks that utilize Wavelength Division Multiplexing (WDM). WDM technology establishes communication between pairs of network nodes by establishing transmitter–receiver paths and assigning wavelengths to each path so that no two paths going through the same fiber link use the same wavelength. Optical bandwidth is the number of distinct wavelengths. Since state–of–the–art technology allows for a limited number of wavelengths, the engineering problem to be solved is to establish communication between pairs of nodes so that the total number of wavelengths used is minimized; this is known as the wavelength routing problem. In this paper we survey recent advances in bandwidth allocation in tree–shaped WDM all–optical networks. We present hardness results and lower bounds for the general problem and the special case of symmetric communication. We give the main ideas of deterministic greedy algorithms and study their limitations. We demonstrate how we can achieve optimal and nearly–optimal bandwidth utilization in networks with wavelength converters using simple algorithms. We also present recent results about the use of randomization for wavelength routing.

One of the most important features in image analysis and understanding is shape. Mathematical morphology is the image processing branch that deals with shape analysis. The definition of all morphological transformations is based on two primitive operations, i.e. dilation and erosion. Since many applications require the solution of morphological problems in real time, researching time efficient algorithms for these two operations is crucial. In this paper efficient parallel algorithms for the binary dilation and erosion are presented and evaluated for an advanced associative processor. Simulation results indicate that the achieved speedup is linear.

In this paper we consider communication issues arising in mobile networks that utilize Frequency Division Multiplexing (FDM) technology. In such networks, many users within the same geographical region can communicate simultaneously with other users of the network using distinct frequencies. The spectrum of available frequencies is limited; thus, efficient solutions to the frequency allocation and the call control problem are essential. In the frequency allocation problem, given users that wish to communicate, the objective is to minimize the required spectrum of frequencies so that communication can be established without signal interference. The objective of the call control problem is, given a spectrum of available frequencies and users that wish to communicate, to maximize the number of users served. We consider cellular, planar, and arbitrary network topologies.

Motion estimation is widely used in video coding schemes in order to reduce the inherent temporal redundancy among the frames of a video stream. In particular, low and very low bit rate video coding schemes need sophisticated motion models which usually require a large number of arithmetic operations. In this paper we present a parallel algorithm for the most practical of these models. Specifically we implement the affine motion model on a hypercube-based multiprocessor. This model covers the most usual kinds of motion and requires only a modest number of arithmetic operations. Also, the hypercube network can efficiently handle the non-regular data flow resulting from the parallel implementation of this model. In addition, we assume that our multiprocessor is fine grained, in contrast to most programmable architectures used in video coding, where processors usually have large local memory. Apart from its practicality, the constraint of limited local memory makes the algorithm design more challenging and thus more theoretically interesting. Finally, with regard to other proposals in the literature, our scheme is more general: whereas our scheme covers all kinds of motion supported by the affine motion model, the rest of the proposals deal only with a subset of these kinds. Copyright © 2000 John Wiley & Sons, Ltd.

We address efficient access to bandwidth in WDM (wavelength division multiplexing) optical networks. We consider tree topologies, ring topologies, as well as trees of rings. These are topologies of concrete practical relevance for which undirected underlying graph models have been studied before by P. Raghavan and E. Upfal (1993). As opposed to previous studies (A. Aggarwal et al., 1993; R. Pankaj, 1992; P. Raghavan and E. Upfal, 1993), we consider directed graph models. Directedness of fiber links is dictated by physical directedness of optical amplifiers. For trees, we give a polynomial time routing algorithm that satisfies requests of maximum load L/sub max/ per fiber link using no more than 15L/sub max//8/spl les/15OPT/8 optical wavelengths. This improves a 2L/sub max/ scheme that is implicit by P. Raghavan and E. Upfal by extending their undirected methods to our directed model. Alternatively stated, for fixed W wavelength technology, we can load the network up to L,, 8W/15 rather than W/2. In engineering terms, this is a so called "6.66% increase of bandwidth" and it is considered substantial. For rings, the approximation factor is 2OPT. For trees of rings, the approximation factor is 15OPT/4. Technically, optical routing requirements give rise to novel coloring paradigms. Our algorithms involve matchings and multicolored alternating cycles, combined with detailed potential and averaging analysis.

The existence of bounded degree networks which can emulate the computation of any bounded degree network of the same size with logarithmic slowdown is well-known. The butterfly is an example of such a universal network. Leiserson was the first to introduce the concept of an area-universal network: a network with VLSI layout area A which can emulate any network of the same size and layout area with logarithmic slowdown. His results imply the existence of an N-node network with layout area O(N log/sup 2/ N) which can emulate any N-node planar network with O(log N) slowdown. The main results of this paper are: There exists an N-node network with layout area O(N log/sup 2/ N) which can emulate any N-node planar network with O(loglogN) slowdown. The N-node butterfly (and hypercube) can emulate any network with VLSI layout area N/sup 2-/spl epsiv// (/spl epsiv/>0) with O(loglogN) slowdown. We also discuss sublogarithmic bounds for the slowdown of emulations of arbitrary bounded degree networks.>

In this paper, we present a new type of graph decomposition called a cut-cover that combines the notions of graph separators and t-neighborhood covers.We show that graphs with good cut-covers can be emulated in hypercubes and butterflies and we show that planar and certain minor-excluded graphs have good cut-covers.In particular, we show how to emulate any N-node bounded degree planar network or any N-node bounded degree graph that excludes KIOgOOl ~as a minor with constant slowdown on hypercube networks.We also show how to emulate any N-node bounded degree planar network or any IV-node bounded degree graph that excludes Ko(l) as a minor with O(log* N) slowdown on butterfly networks.

We show that sorting an input of size N = nz can be performed by an n x n mesh-connected processor array in 2n + O(n) parallel communication steps and using constant-size queues, with high probability.This result is optimal to within a low order additive term, realizing the obvious diameter lower bound.The best previously known algorithm for this problem required 2.5n + o(n) steps.Our techniques can be applied to higher dimensional meshes as well as torus-connected networks, achieving significantly better bounds than the known results.computers.While its diameter is large in comparison to other well-studied networks (e.g., hypercube, butterfly, shuffle-exchange networks), the simplicity and regularity of its interconnection pattern make it ideal for VLSI implementation.Recent work by Dally [Da187] suggests that high diameter networks such as the mesh may provide a more efficient communication medium for VLSI-based parallel computers.Furthermore, a large number of efficient algorithms have been

Article Free Access Share on Simple path selection for optimal routing on processor arrays Authors: Christos Kaklamanis View Profile , Danny Krizanc View Profile , Satish Rao View Profile Authors Info & Claims SPAA '92: Proceedings of the fourth annual ACM symposium on Parallel algorithms and architecturesJune 1992 Pages 23–30https://doi.org/10.1145/140901.140904Published:01 June 1992Publication History 13citation290DownloadsMetricsTotal Citations13Total Downloads290Last 12 Months12Last 6 weeks7 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

In this paper we investigate the parallel complexity of the backtrack and branch-and-bound search on the mesh-connected array.We present an Q(~/-) lower bound for the time needed by a randomized algorithm to perform backtrack and branch-and-bound search of a tree of depth d on the ~x fl mesh, even when the depth of the tree is known in advance.The lower bound holds also for algorithms that are allowed to move tree-nodes and create multiple copies of the same tre~node.For the upper bounds we give deterministic algorithms that are within a factor of O(log ~N) from our lower bound.Our algorithms do not make any assumption on the shape of the tree to be searched, do not know the depth of the tree in advance and do not move tree-nodes nor create multiple copies of the same node; also, they guarantee optimal load and only need constant-sized buffers.The best previously known algorithm for backtrack search on the mesh was randomized and required O(d@/ log N) time.Our algorithm for branch-andbound is the first algorithm that performs branch-andbound search on a sparae network.Both the lower and the upper bounds extend to higher dimension meshes.

we show that sorting an input of size N = n2 can be performed by an n x n mesh-connected processor array in 2.5n + o(n) parallel communication steps and using constant size queues, with high probability.The best previously known algorithm for this problem required 37L + o(n) steps.We also show that selecting the element of rank k out of N = n2 inputs on an n x n mesh can be performed in 1.25n + o(n) steps and using constant size queues, with high probability.The best previously known algorithm for this problem involved sorting, and required 3n + o(n) steps.Both of our algorithms can be generalized to higher dimensions, achieving bounds better than the known results.

The computational power of 2-D and 3-D processor arrays that contain a potentially large number of faults is analyzed. Both a random and a worst-case fault model are considered, and it is proved that in either scenario low-dimensional arrays are surprisingly fault tolerant. It is also shown how to route, sort, and perform systolic algorithms for problems such as matrix multiplication in optimal time on faulty arrays. In many cases, the running time is the same as if there were no faults in the array (up to constant factors). On the negative side, it is shown that any constant congestion embedding of an n*n fault-free array on an n*n array with Theta (n/sup 2/) random faults (or Theta (log n) worst-case faults) requires dilation Theta (log n). For 3-D arrays, knot theory is used to prove that the required dilation is Omega ( square root log n).>

Article Free Access Share on Tight bounds for oblivious routing in the hypercube Authors: C. Kaklamanis Aiken Computation Laboratory, Harvard University, Cambridge, MA Aiken Computation Laboratory, Harvard University, Cambridge, MAView Profile , D. Krizanc Department of Computer Science, University of Rochester, Rochester, NY Department of Computer Science, University of Rochester, Rochester, NYView Profile , T. Tsantilas Aiken Computation Laboratory, Harvard University, Cambridge, MA Aiken Computation Laboratory, Harvard University, Cambridge, MAView Profile Authors Info & Claims SPAA '90: Proceedings of the second annual ACM symposium on Parallel algorithms and architecturesMay 1990 Pages 31–36https://doi.org/10.1145/97444.97453Published:01 May 1990Publication History 57citation682DownloadsMetricsTotal Citations57Total Downloads682Last 12 Months63Last 6 weeks8 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF