Source author record

Joshua R. Wang

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms

Catalog footprint

Research overview

2works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Scheduling with Communication Delay in Near-Linear Time

We consider the problem of efficiently scheduling jobs with precedence constraints on a set of identical machines in the presence of a uniform communication delay. Such precedence-constrained jobs can be modeled as a directed acyclic graph, $G = (V, E)$ . In this setting, if two precedence-constrained jobs $u$ and $v$ , with $v$ dependent on $u$ ( $u \prec v$ ), are scheduled on different machines, then $v$ must start at least $ρ$ time units after $u$ completes. The scheduling objective is to minimize makespan, i.e. the total time from when the first job starts to when the last job finishes. The focus of this paper is to provide an efficient approximation algorithm with near-linear running time. We build on the algorithm of Lepere and Rapine [STACS 2002] for this problem to give an $O\left(\frac{\ln ρ}{\ln \ln ρ} \right)$ -approximation algorithm that runs in $\tilde{O}(|V| + |E|)$ time.

preprint2016arXiv

Deterministic Time-Space Tradeoffs for k-SUM

Given a set of numbers, the $k$ -SUM problem asks for a subset of $k$ numbers that sums to zero. When the numbers are integers, the time and space complexity of $k$ -SUM is generally studied in the word-RAM model; when the numbers are reals, the complexity is studied in the real-RAM model, and space is measured by the number of reals held in memory at any point. We present a time and space efficient deterministic self-reduction for the $k$ -SUM problem which holds for both models, and has many interesting consequences. To illustrate: * $3$ -SUM is in deterministic time $O(n^2 \lg\lg(n)/\lg(n))$ and space $O\left(\sqrt{\frac{n \lg(n)}{\lg\lg(n)}}\right)$ . In general, any polylogarithmic-time improvement over quadratic time for $3$ -SUM can be converted into an algorithm with an identical time improvement but low space complexity as well. * $3$ -SUM is in deterministic time $O(n^2)$ and space $O(\sqrt n)$ , derandomizing an algorithm of Wang. * A popular conjecture states that 3-SUM requires $n^{2-o(1)}$ time on the word-RAM. We show that the 3-SUM Conjecture is in fact equivalent to the (seemingly weaker) conjecture that every $O(n^{.51})$ -space algorithm for $3$ -SUM requires at least $n^{2-o(1)}$ time on the word-RAM. * For $k \ge 4$ , $k$ -SUM is in deterministic $O(n^{k - 2 + 2/k})$ time and $O(\sqrt{n})$ space.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.