Zobrazeno 1 - 10
of 45
pro vyhledávání: '"Umboh, Seeun William"'
In this paper, we study the Dynamic Parameterized Subset Sampling (DPSS) problem in the Word RAM model. In DPSS, the input is a set,~$S$, of~$n$ items, where each item,~$x$, has a non-negative integer weight,~$w(x)$. Given a pair of query parameters,
Externí odkaz:
http://arxiv.org/abs/2409.18036
Probabilistic metric embedding into trees is a powerful technique for designing online algorithms. The standard approach is to embed the entire underlying metric into a tree metric and then solve the problem on the latter. The overhead in the competi
Externí odkaz:
http://arxiv.org/abs/2408.16298
The net frequency (NF) of a string, of length $m$, in a text, of length $n$, is the number of occurrences of the string in the text with unique left and right extensions. Recently, Guo et al. [CPM 2024] showed that NF is combinatorially interesting a
Externí odkaz:
http://arxiv.org/abs/2408.00308
The online joint replenishment problem (JRP) is a fundamental problem in the area of online problems with delay. Over the last decade, several works have studied generalizations of JRP with different cost functions for servicing requests. Most prior
Externí odkaz:
http://arxiv.org/abs/2407.15809
We consider the Max Unique Coverage problem, including applications to the data stream model. The input is a universe of $n$ elements, a collection of $m$ subsets of this universe, and a cardinality constraint, $k$. The goal is to select a subcollect
Externí odkaz:
http://arxiv.org/abs/2407.09368
We initiate the study of online problems with set delay, where the delay cost at any given time is an arbitrary function of the set of pending requests. In particular, we study the online min-cost perfect matching with set delay (MPMD-Set) problem, w
Externí odkaz:
http://arxiv.org/abs/2211.02394
Autor:
Cao, Nairen, Fineman, Jeremy T., Li, Shi, Mestre, Julián, Russell, Katina, Umboh, Seeun William
The active-time scheduling problem considers the problem of scheduling preemptible jobs with windows (release times and deadlines) on a parallel machine that can schedule up to $g$ jobs during each timestep. The goal in the active-time problem is to
Externí odkaz:
http://arxiv.org/abs/2207.12507
Publikováno v:
In Transportation Research Part B December 2024 190
We initiate the theoretical study of Ext-TSP, a problem that originates in the area of profile-guided binary optimization. Given a graph $G=(V, E)$ with positive edge weights $w: E \rightarrow R^+$, and a non-increasing discount function $f(\cdot)$ s
Externí odkaz:
http://arxiv.org/abs/2107.07815
Let $P=\{p_0,\ldots,p_{n-1}\}$ be a set of points in $\mathbb{R}^d$, modeling devices in a wireless network. A range assignment assigns a range $r(p_i)$ to each point $p_i\in P$, thus inducing a directed communication graph $G_r$ in which there is a
Externí odkaz:
http://arxiv.org/abs/2009.14473