Author name cluster

Richard Cole

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.

9 papers

1 author row

NeurIPS Conference 2025 Conference Paper

Parsimonious Predictions for Strategyproof Scheduling

Richard Cole
Anupam Gupta
Pranav Jangir

We consider the problem of scheduling $m$ jobs on $n$ unrelated strategic machines to minimize the maximum load of any machine, but the machines are strategic and may misreport processing times to minimize their own load. The pioneering work of Nisan and Ronen gave an $n$-approximate deterministic strategyproof mechanism for this setting, and this was recently shown to be best possible by the breakthrough results of Christodoulou et al. This large approxation guarantee begs the question: how can we avoid these large worst-case results. In this work, we use the powerful framework of algorithms with (machine-learned) predictions to bypass these strong impossibility results. We show how we can predict $O(m+n)$ values to obtain a deterministic strategyproof algorithm whose makespan is within a constant factor of the optimal makespan when the predictions are correct, and $O(n)$ times the optimum no matter how poor the predictions are.

PDF Details

IJCAI Conference 2018 Conference Paper

When Does Diversity of Agent Preferences Improve Outcomes in Selfish Routing?

Richard Cole
Thanasis Lianeas
Evdokia Nikolova

We seek to understand when heterogeneity in agent preferences yields improved outcomes in terms of overall cost. That this might be hoped for is based on the common belief that diversity is advantageous in many multi-agent settings. We investigate this in the context of routing. Our main result is a sharp characterization of the network settings in which diversity always helps, versus those in which it is sometimes harmful. Specifically, we consider routing games, where diversity arises in the way that agents trade-off two criteria (such as time and money, or, in the case of stochastic delays, expectation and variance of delay). Our main contributions are: 1) A participant-oriented measure of cost in the presence of agent diversity; 2) A full characterization of those network topologies for which diversity always helps, for all latency functions and demands.

PDF Details

AAMAS Conference 2013 Conference Paper

Positive Results for Mechanism Design without Money

Richard Cole
Vasilis Gkatzelis
Gagan Goel

Consider the problem of allocating multiple divisible goods to two agents in a strategy-proof fashion without the use of payments or priors. Previous work [1, 2] has aimed at implementing allocations that are competitive with respect to an appropriately defined measure of social welfare. These results have mostly been negative, proving that no dictatorial mechanism can achieve an approximation factor better than 0. 5, and leaving open the question of whether there exists a non-dictatorial mechanism that outperforms this bound. We provide a positive answer to this question by presenting an interesting non-dictatorial mechanism that achieves an approximation factor of 2/3 for this measure of social welfare. In proving this bound we also touch on the issue of fairness: we show that the proportionally fair solution, a well known fairness concept for money-free settings, is highly competitive with respect to social welfare. We then show how to use the proportionally fair solution to design our non-dictatorial strategy-proof mechanism.

PDF

TCS Journal 2007 Journal Article

A unified access bound on comparison-based dynamic dictionaries

Mihai Bădoiu
Richard Cole
Erik D. Demaine
John Iacono

We present a dynamic comparison-based search structure that supports insertions, deletions, and searches within the unified bound. The unified bound specifies that it is quick to access an element that is near a recently accessed element. More precisely, if w ( y ) distinct elements have been accessed since the last access to element y, and d ( x, y ) denotes the rank distance between x and y among the current set of elements, then the amortized cost to access element x is O ( min y log [ w ( y ) + d ( x, y ) + 2 ] ). This property generalizes the working-set and dynamic-finger properties of splay trees.

Details DOI

I&C Journal 2004 Journal Article

Parallel two dimensional witness computation

Richard Cole
Zvi Galil
Ramesh Hariharan
S. Muthukrishnan
Kunsoo Park

An optimal parallel CRCW-PRAM algorithm to compute witnesses for all non-period vectors of an m 1×m 2 pattern is given. The algorithm takes O(loglogm) time and does O(m 1×m 2) work, where m=max{m 1, m 2}. This yields a work optimal algorithm for 2D pattern matching which takes O(loglogm) preprocessing time and O(1) text processing time.

Details DOI

I&C Journal 2003 Journal Article

Overlap matching

Amihood Amir
Richard Cole
Ramesh Hariharan
Moshe Lewenstein
Ely Porat

We propose a new paradigm for string matching, namely structural matching. In structural matching, the text and pattern contents are not important. Rather, some areas in the text and pattern, such as intervals, are singled out. A “match” is a text location where a specified relation between the text and pattern areas is satisfied. In particular we define the structural matching problem of overlap (parity) matching. We seek the text locations where all overlaps of the given pattern and text intervals have even length. We show that this problem can be solved in time O(nlogm), where the text length is n and the pattern length is m. As an application of overlap matching, we show how to reduce the string matching with swaps problem to the overlap matching problem. The string matching with swaps problem is the problem of string matching in the presence of local swaps. The best deterministic upper bound known for this problem was O(nm 1/3logmlogσ) for a general alphabet Σ, where σ=min(m, |Σ|). Our reduction provides a solution to the pattern matching with swaps problem in time O(nlogmlogσ).

Details DOI

I&C Journal 1991 Journal Article

Approximate parallel scheduling. II. Applications to logarithmic-time optimal parallel graph algorithms

Richard Cole
Uzi Vishkin

Part I of this paper presented a novel technique for approximate parallel scheduling and a new logarithmic time optimal parallel algorithm for the list ranking problem. In this part, we give a new logarithmic time parallel (PRAM) algorithm for computing the connected components of undirected graphs which uses this scheduling technique. The connectivity algorithm is optimal unless m = o(n log ∗ n) in graphs of n vertices and m edges. (log(k) denotes the kth iterate of the log function and log ∗ n denotes the least i such that log(i) n ≤ 2). Using known results, this new algorithm implies logarithmic time optimal parallel algorithms for a number of other graph problems, including biconnectivity, Euler tours, strong orientation and st-numbering. Another contribution of the present paper is a parallel union/find algorithm.

Details DOI

I&C Journal 1989 Journal Article

Faster optimal parallel prefix sums and list ranking

Richard Cole
Uzi Vishkin

We present a parallel algorithm for the prefix sums problem which runs in timeO( logn/log logn) usingnlog logn/lognprocessors (optimal speedup). This algorithm leads to a parallel list ranking algorithm which runs inO(logn) time usingn/lognprocessors (optimal speedup).

Details DOI

TCS Journal 1987 Journal Article

Partitioning point sets in arbitrary dimension

Richard Cole

We introduce a new type of partition called a parallel planes partition. We prove there exists a parallel planes partition of any set of n points in arbitrary dimension. This partition yields a data structure for the half-space retrieval problem in arbitrary dimension; it has linear size and achieves a sublinear query time. Also, we give efficient algorithms for computing this partition.

Details DOI