Arrow Research search

Author name cluster

Ashish Goel

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

40 papers
2 author rows

Possible papers

40

NeurIPS Conference 2021 Conference Paper

Robust Allocations with Diversity Constraints

  • Zeyu Shen
  • Lodewijk Gelauff
  • Ashish Goel
  • Aleksandra Korolova
  • Kamesh Munagala

We consider the problem of allocating divisible items among multiple agents, and consider the setting where any agent is allowed to introduce {\emph diversity constraints} on the items they are allocated. We motivate this via settings where the items themselves correspond to user ad slots or task workers with attributes such as race and gender on which the principal seeks to achieve demographic parity. We consider the following question: When an agent expresses diversity constraints into an allocation rule, is the allocation of other agents hurt significantly? If this happens, the cost of introducing such constraints is disproportionately borne by agents who do not benefit from diversity. We codify this via two desiderata capturing {\em robustness}. These are {\emph no negative externality} -- other agents are not hurt -- and {\emph monotonicity} -- the agent enforcing the constraint does not see a large increase in value. We show in a formal sense that the Nash Welfare rule that maximizes product of agent values is {\emph uniquely} positioned to be robust when diversity constraints are introduced, while almost all other natural allocation rules fail this criterion. We also show that the guarantees achieved by Nash Welfare are nearly optimal within a widely studied class of allocation rules. We finally perform an empirical simulation on real-world data that models ad allocations to show that this gap between Nash Welfare and other rules persists in the wild.

PDF Details

JAIR Journal 2019 Journal Article

Iterative Local Voting for Collective Decision-making in Continuous Spaces

  • Nikhil Garg
  • Vijay Kamble
  • Ashish Goel
  • David Marn
  • Kamesh Munagala

Many societal decision problems lie in high-dimensional continuous spaces not amenable to the voting techniques common for their discrete or single-dimensional counterparts. These problems are typically discretized before running an election or decided upon through negotiation by representatives. We propose a algorithm called Iterative Local Voting for collective decision-making in this setting. In this algorithm, voters are sequentially sampled and asked to modify a candidate solution within some local neighborhood of its current value, as defined by a ball in some chosen norm, with the size of the ball shrinking at a specified rate. We first prove the convergence of this algorithm under appropriate choices of neighborhoods to Pareto optimal solutions with desirable fairness properties in certain natural settings: when the voters' utilities can be expressed in terms of some form of distance from their ideal solution, and when these utilities are additively decomposable across dimensions. In many of these cases, we obtain convergence to the societal welfare maximizing solution.We then describe an experiment in which we test our algorithm for the decision of the U.S. Federal Budget on Mechanical Turk with over 2,000 workers, employing neighborhoods defined by various L-Norm balls. We make several observations that inform future implementations of such a procedure.

PDF Details DOI

AAAI Conference 2019 Conference Paper

Random Dictators with a Random Referee: Constant Sample Complexity Mechanisms for Social Choice

  • Brandon Fain
  • Ashish Goel
  • Kamesh Munagala
  • Nina Prabhu

We study social choice mechanisms in an implicit utilitarian framework with a metric constraint, where the goal is to minimize Distortion, the worst case social cost of an ordinal mechanism relative to underlying cardinal utilities. We consider two additional desiderata: Constant sample complexity and Squared Distortion. Constant sample complexity means that the mechanism (potentially randomized) only uses a constant number of ordinal queries regardless of the number of voters and alternatives. Squared Distortion is a measure of variance of the Distortion of a randomized mechanism. Our primary contribution is the first social choice mechanism with constant sample complexity and constant Squared Distortion (which also implies constant Distortion). We call the mechanism Random Referee, because it uses a random agent to compare two alternatives that are the favorites of two other random agents. We prove that the use of a comparison query is necessary: no mechanism that only elicits the top-k preferred alternatives of voters (for constant k) can have Squared Distortion that is sublinear in the number of alternatives. We also prove that unlike any top-k only mechanism, the Distortion of Random Referee meaningfully improves on benign metric spaces, using the Euclidean plane as a canonical example. Finally, among top-1 only mechanisms, we introduce Random Oligarchy. The mechanism asks just 3 queries and is essentially optimal among the class of such mechanisms with respect to Distortion. In summary, we demonstrate the surprising power of constant sample complexity mechanisms generally, and just three random voters in particular, to provide some of the best known results in the implicit utilitarian framework.

PDF Details

IJCAI Conference 2016 Conference Paper

Probabilistic Matrix Inspection and Group Scheduling

  • Hooyeon Lee
  • Ashish Goel

Consider an event organizer who is trying to schedule a group meeting. Availability of agents is unknown to the organizer a priori, but the organizer may have probability estimates on availability of each agent for each date/time option. The organizer can ask an agent to reveal her availability, but it causes inconvenience for the agent, and thus the organizer wishes to find an agreeable outcome at a minimum number of such queries. Motivated by this example, we study the Probabilistic Matrix Inspection problem in which we are given a matrix of Bernoulli random variables that are mutually independent, and the objective is to determine whether the matrix contains a column consisting only of 1's. We are allowed to inspect an arbitrary entry at unit cost, which reveals the realization of the entry, and we wish to find an inspection policy whose expected number of inspections is minimum. We first show that an intuitive greedy algorithm exists for 1-row and 1-column matrices, and we generalize this to design an algorithm that finds an optimal policy in polynomial time for the general case.

PDF Details

SODA Conference 2014 Conference Paper

Disjoint Set Union with Randomized Linking

  • Ashish Goel
  • Sanjeev Khanna
  • Daniel H. Larkin
  • Robert Endre Tarjan

A classic result in the analysis of data structures is that path compression with linking by rank solves the disjoint set union problem in almost-constant amortized time per operation. Recent experiments suggest that in practice, a naïve linking method works just as well if not better than linking by rank, in spite of being theoretically inferior. How can this be? We prove that randomized linking is asymptotically as efficient as linking by rank. This result provides theory that matches the experiments, which implicitly do randomized linking as a result of the way the input instances are generated.

Details

JMLR Journal 2013 Journal Article

Dimension Independent Similarity Computation

  • Reza Bosagh Zadeh
  • Ashish Goel

We present a suite of algorithms for Dimension Independent Similarity Computation (DISCO) to compute all pairwise similarities between very high-dimensional sparse vectors. All of our results are provably independent of dimension, meaning that apart from the initial cost of trivially reading in the data, all subsequent operations are independent of the dimension; thus the dimension can be very large. We study Cosine, Dice, Overlap, and the Jaccard similarity measures. For Jaccard similarity we include an improved version of MinHash. Our results are geared toward the MapReduce framework. We empirically validate our theorems with large scale experiments using data from the social networking site Twitter. At time of writing, our algorithms are live in production at twitter.com. [abs] [ pdf ][ bib ] &copy JMLR 2013. ( edit, beta )

PDF Details

SODA Conference 2012 Conference Paper

On the communication and streaming complexity of maximum bipartite matching

  • Ashish Goel
  • Michael Kapralov
  • Sanjeev Khanna

Consider the following communication problem. Alice holds a graph G A = ( P, Q, E A ) and Bob holds a graph G B = ( P, Q, E B ), where | P | = | Q | = n. Alice is allowed to send Bob a message m that depends only on the graph G A. Bob must then output a matching M ⊆ E A ∪ E B. What is the minimum message size of the message m that Alice sends to Bob that allows Bob to recover a matching of size at least (1 − ∊) times the maximum matching in G A ∪ G B? The minimum message length is the one-round communication complexity of approximating bipartite matching. It is easy to see that the one-round communication complexity also gives a lower bound on the space needed by a one-pass streaming algorithm to compute a (1 − ∊)-approximate bipartite matching. The focus of this work is to understand one-round communication complexity and one-pass streaming complexity of maximum bipartite matching. In particular, how well can one approximate these problems with linear communication and space? Prior to our work, only a ½-approximation was known for both these problems. In order to study these questions, we introduce the concept of an ∊-matching cover of a bipartite graph G, which is a sparse subgraph of the original graph that preserves the size of maximum matching between every subset of vertices to within an additive en error. We give a polynomial time construction of a ½-matching cover of size O ( n ) with some crucial additional properties, thereby showing that Alice and Bob can achieve a ⅔-approximation with a message of size O ( n ). While we do not provide bounds on the size of ∊-matching covers for ∊ < 1/2, we prove that in general, the size of the smallest ∊-matching cover of a graph G on n vertices is essentially equal to the size of the largest so-called ∊-Ruzsa Szemerédi graph on n vertices. We use this connection to show that for any δ > 0, a (⅔ + δ)-approximation requires a communication complexity of n 1+Ω(1/ log log n ). We also consider the natural restrictingon of the problem in which G A and G B are only allowed to share vertices on one side of the bipartition, which is motivated by applications to one-pass streaming with vertex arrivals. We show that a ¾ -approximation can be achieved with a linear size message in this case, and this result is best possible in that super-linear space is needed to achieve any better approximation. Finally, we build on our techniques for the restricted version above to design one-pass streaming algorithm for the case when vertices on one side are known in advance, and the vertices on the other side arrive in a streaming manner together with all their incident edges. This is precisely the setting of the celebrated (1 − 1/ε)-competitive randomized algorithm of Karp-Vazirani-Vazirani (KVV) for the online bipartite matching problem [12]. We present here the first deterministic one-pass streaming (1 − 1/ε)-approximation algorithm using O ( n ) space for this setting.

Details

FOCS Conference 2010 Conference Paper

One Tree Suffices: A Simultaneous O(1)-Approximation for Single-Sink Buy-at-Bulk

  • Ashish Goel
  • Ian Post

We study the single-sink buy-at-bulk problem with an unknown cost function. We wish to route flow from a set of demand nodes to a root node, where the cost of routing x total flow along an edge is proportional to f(x) for some concave, non-decreasing function f satisfying f(0)=0. We present a simple, fast, combinatorial algorithm that takes a set of demands and constructs a single tree T such that for all f the cost f(T) is a 47. 45-approximation of the optimal cost for that f. This is within a factor of 2. 33 of the best approximation ratio currently achievable when the tree can be optimized for a specific function. Trees achieving simultaneous O(1)-approximations for all concave functions were previously not known to exist regardless of computation time.

Details

STOC Conference 2010 Conference Paper

Perfect matchings in o( n log n ) time in regular bipartite graphs

  • Ashish Goel
  • Michael Kapralov
  • Sanjeev Khanna

In this paper we consider the well-studied problem of finding a perfect matching in a d-regular bipartite graph on 2n nodes with m=nd edges. The best-known algorithm for general bipartite graphs (due to Hopcroft and Karp) takes time O(m√n). In regular bipartite graphs, however, a matching is known to be computable in O(m) time (due to Cole, Ost, and Schirra). In a recent line of work by Goel, Kapralov, and Khanna the O(m) time bound was improved first to ~ O(min m, n 2.5 /d) and then to ~O(min {m, n 2 /d\}). In this paper, we give a randomized algorithm that finds a perfect matching in a d-regular graph and runs in O(n log n) time (both in expectation and with high probability). The algorithm performs an appropriately truncated alternating random walk to successively find augmenting paths. Our algorithm may be viewed as using adaptive uniform sampling, and is thus able to bypass the limitations of (non-adaptive) uniform sampling established in earlier work. Our techniques also give an algorithm that successively finds a matching in the support of a doubly stochastic matrix in expected time O(n log 2 n), with O(m) pre-processing time; this gives a simple O(m+mn log 2 n) time algorithm for finding the Birkhoff-von Neumann decomposition of a doubly stochastic matrix. We show that randomization is crucial for obtaining o(nd) time algorithms by establishing an Ω(nd) lower bound for deterministic algorithms. We also show that there does not exist a randomized algorithm that finds a matching in a regular bipartite multigraph and takes o(n log n) time with high probability.

Details

FOCS Conference 2009 Conference Paper

An Oblivious O(1)-Approximation for Single Source Buy-at-Bulk

  • Ashish Goel
  • Ian Post

We consider the single-source (or single-sink) buy-at-bulk problem with an unknown concave cost function. We want to route a set of demands along a graph to or from a designated root node, and the cost of routing x units of flow along an edge is proportional to some concave, non-decreasing function f such that f(0) = 0. We present a polynomial time algorithm that finds a distribution over trees such that the expected cost of a tree for any f is within an O(1)-factor of the optimum cost for that f. The previous best simultaneous approximation for this problem, even ignoring computation time, was O(log |D|), where D is the multi-set of demand nodes. We design a simple algorithmic framework using the ellipsoid method that finds an O(1)-approximation if one exists, and then construct a separation oracle using a novel adaptation of the Guha, Meyerson, and Munagala algorithm for the single-sink buy-at-bulk problem that proves an O(1) approximation is possible for all f. The number of trees in the support of the distribution constructed by our algorithm is at most 1+log |D|.

Details

STOC Conference 2004 Conference Paper

Multi-processor scheduling to minimize flow time with epsilon resource augmentation

  • Chandra Chekuri
  • Ashish Goel
  • Sanjeev Khanna
  • Amit Kumar 0001

We investigate the problem of online scheduling of jobs to minimize flow time and stretch on m identical machines. We consider the case where the algorithm is given either (1+ε)m machines or m machines of speed (1+ε), for arbitrarily small ε > 0. We show that simple randomized and deterministic load balancing algorithms, coupled with simple single machine scheduling strategies such as SRPT (shortest remaining processing time) and SJF (shortest job first), are O(poly(1/ε))-competitive for both flow time and stretch. These are the first results which prove constant factor competitive ratios for flow time or stretch with arbitrarily small resource augmentation. Both the randomized and the deterministic load balancing algorithms are non-migratory and do immediate dispatch of jobs.The randomized algorithm just allocates each incoming job to a random machine. Hence this algorithm is non-clairvoyant, and coupled with SETF (shortest elapsed time first), yields the first non-clairvoyant algorithm which is constant competitive for minimizing flow time with arbitrarily small resource augmentation. The deterministic algorithm that we analyze is due to Avrahami and Azar. For this algorithm, we show O(1/ε)-competitiveness for total flow time and stretch, and also for their L p norms, for any fixed p ≥ 1.

Details

STOC Conference 2004 Conference Paper

Sharp thresholds For monotone properties in random geometric graphs

  • Ashish Goel
  • Sanatan Rai
  • Bhaskar Krishnamachari

Random geometric graphs result from taking n uniformly distributed points in the unit cube, [0,1] d , and connecting two points if their Euclidean distance is at most r, for some prescribed r. We show that monotone properties for this class of graphs have sharp thresholds by reducing the problem to bounding the bottleneck matching on two sets of $n$ points distributed uniformly in [0,1] d . We present upper bounds on the threshold width, and show that our bound is sharp for d = 1 and at most a sublogarithmic factor away for d ≥ 2. Interestingly, the threshold width is much sharper for random geometric graphs than for Bernoulli random graphs. Further, a random geometric graph is shown to be a subgraph, with high probability, of another independently drawn random geometric graph with a slightly larger radius; this property is shown to have no analogue for Bernoulli random graphs.

Details

FOCS Conference 2003 Conference Paper

Instability of FIFO at Arbitrarily Low Rates in the Adversarial Queueing Model

  • Rajat Bhattacharjee
  • Ashish Goel

We study the stability of the commonly used packet forwarding protocol, FIFO (First In First Out), in the adversarial queuing model. We prove that FIFO can become unstable, i. e. , lead to unbounded buffer-occupancies and queuing delays, at arbitrarily low injection rates. In order to demonstrate instability at rate r, we use a network of size polynomial in 1/r.

Details

FOCS Conference 2001 Conference Paper

Source Routing and Scheduling in Packet Networks

  • Matthew Andrews
  • Antonio Fernández 0001
  • Ashish Goel
  • Lisa Zhang 0001

We study routing and scheduling in packet-switched networks. We assume an adversary that controls the injection time, source, and destination for each packet injected. A set of paths for these packets is admissible if no link in the network is overloaded. We present the first on-line routing algorithm that finds a set of admissible paths whenever this is feasible. Our algorithm calculates a path for each packet as soon as it is injected at its source using a simple shortest path computation. The length of a link reflects its current congestion. We also show how our algorithm can be implemented under today's Internet routing paradigms. When the paths are known (either given by the adversary or computed as above) our goal is to schedule the packets along the given paths so that the packets experience small end-to-end delays. The best previous delay bounds for deterministic and distributed scheduling protocols were exponential in the path length. In this paper we present the first deterministic and distributed scheduling protocol that guarantees a polynomial end-to-end delay for every packet. Finally, we discuss the effects of combining routing with scheduling. We first show that some, unstable scheduling protocols remain unstable no matter how the paths are chosen. However, the freedom to choose paths can make a difference. For example, we show that a ring with parallel links is stable for all greedy scheduling protocols if paths are chosen intelligently, whereas this is not the case if the adversary specifies the paths.

Details

FOCS Conference 1999 Conference Paper

Stochastic Load Balancing and Related Problems

  • Ashish Goel
  • Piotr Indyk

We study the problems of makespan minimization (load balancing), knapsack, and bin packing when the jobs have stochastic processing requirements or sizes. If the jobs are all Poisson, we present a two approximation for the first problem using Graham's rule, and observe that polynomial time approximation schemes can be obtained for the last two problems. If the jobs are all exponential, we present polynomial time approximation schemes for all three problems. We also obtain quasi-polynomial time approximation schemes for the last two problems if the jobs are Bernoulli variables.

Details

FOCS Conference 1998 Conference Paper

Approximating a Finite Metric by a Small Number of Tree Metrics

  • Moses Charikar
  • Chandra Chekuri
  • Ashish Goel
  • Sudipto Guha
  • Serge A. Plotkin

Y. Bartal (1996, 1998) gave a randomized polynomial time algorithm that given any n point metric G, constructs a tree T such that the expected stretch (distortion) of any edge is at most O (log n log log n). His result has found several applications and in particular has resulted in approximation algorithms for many graph optimization problems. However approximation algorithms based on his result are inherently randomized. In this paper we derandomize the use of Bartal's algorithm in the design of approximation algorithms. We give an efficient polynomial time algorithm that given a finite n point metric G, constructs O(n log n) trees and a probability distribution /spl mu/ on them such that the expected stretch of any edge of G in a tree chosen according to /spl mu/ is at most O(log n log log n). Our result establishes that finite metrics can be probabilistically approximated by a small number of tree metrics. We obtain the first deterministic approximation algorithms for buy-at-bulk network design and vehicle routing; in addition we subsume results from our earlier work on derandomization. Our main result is obtained by a novel view of probabilistic approximation of metric spaces as a deterministic optimization problem via linear programming.

Details