Zobrazeno 1 - 10
of 230
pro vyhledávání: '"Moseley, Benjamin"'
Many modern computing workloads are composed of parallelizable jobs. A single parallelizable job can be completed more quickly if it is run on additional servers, however each job is typically limited in the number of servers it can run on (its paral
Externí odkaz:
http://arxiv.org/abs/2404.00346
Best of Many in Both Worlds: Online Resource Allocation with Predictions under Unknown Arrival Model
Online decision-makers often obtain predictions on future variables, such as arrivals, demands, inventories, and so on. These predictions can be generated from simple forecasting algorithms for univariate time-series, all the way to state-of-the-art
Externí odkaz:
http://arxiv.org/abs/2402.13530
This paper leverages the framework of algorithms-with-predictions to design data structures for two fundamental dynamic graph problems: incremental topological ordering and cycle detection. In these problems, the input is a directed graph on $n$ node
Externí odkaz:
http://arxiv.org/abs/2402.11028
Datalogo is an extension of Datalog that allows for aggregation and recursion over an arbitrary commutative semiring. Like Datalog, Datalogo programs can be evaluated via the natural iterative algorithm until a fixed point is reached. However unlike
Externí odkaz:
http://arxiv.org/abs/2312.14063
The classical ski-rental problem admits a textbook 2-competitive deterministic algorithm, and a simple randomized algorithm that is $\frac{e}{e-1}$-competitive in expectation. The randomized algorithm, while optimal in expectation, has a large varian
Externí odkaz:
http://arxiv.org/abs/2308.05067
This paper considers correlation clustering on unweighted complete graphs. We give a combinatorial algorithm that returns a single clustering solution that is simultaneously $O(1)$-approximate for all $\ell_p$-norms of the disagreement vector; in oth
Externí odkaz:
http://arxiv.org/abs/2308.01534
We revisit the online dynamic acknowledgment problem. In the problem, a sequence of requests arrive over time to be acknowledged, and all outstanding requests can be satisfied simultaneously by one acknowledgement. The goal of the problem is to minim
Externí odkaz:
http://arxiv.org/abs/2305.18227
A growing line of work shows how learned predictions can be used to break through worst-case barriers to improve the running time of an algorithm. However, incorporating predictions into data structures with strong theoretical guarantees remains unde
Externí odkaz:
http://arxiv.org/abs/2305.10536
The classic newsvendor model yields an optimal decision for a "newsvendor" selecting a quantity of inventory, under the assumption that the demand is drawn from a known distribution. Motivated by applications such as cloud provisioning and staffing,
Externí odkaz:
http://arxiv.org/abs/2305.07993