In vertex recoloring, we are given $n$ vertices with their initial coloring, and edges arrive in an online fashion. The algorithm must maintain a valid coloring by recoloring vertices, at cost. problem abstracts scenario of job placement machines (possibly the cloud), where represent jobs, colors machines, ``anti affinity'' (disengagement) constraints. Online is hard problem. One family instances which fairly well-understood bipartite graphs, two sufficient to satisfy all this case it known...

We develop a new approach for online network design and obtain improved competitive ratios several problems. Our gives natural deterministic algorithms simple analyses. At the heart of our work is novel application embeddings into hierarchically well-separated trees (HSTs) to analysis --- we charge cost algorithm optimal solution on any HST embedding terminals. This technique widely applicable many problems unified framework design.In sense, brings together two main approaches design. The...

We develop a new approach for online network design and obtain improved competitive ratios several problems. Our gives natural deterministic algorithms simple analyses. At the heart of our work is novel application embeddings into hierarchically well-separated trees (HSTs) to analysis — we charge cost algorithm optimal solution on any HST embedding terminals. This technique widely applicable many problems unified framework design.

We give a general approach for solving optimization problems on noisy minor free and bounded treewidth graphs, where fraction of edges are adversarially corrupted. The setting was first considered by Magen Moharrami they gave (1 + ϵ)-estimation algorithm the independent set problem. Later, Chan Har-Peled designed local search that finds ϵ)-approximate set. However, nothing known regarding other in setting. Our main contribution is LP-based framework yields ϵ)-approximation algorithms MAX-k-CSPs.

The online (uniform) buy-at-bulk network design problem asks us to a network, where the edge-costs exhibit economy-of-scale. Previous approaches this used tree-embeddings, giving randomized algorithms. Moreover, optimal results with logarithmic competitive ratio requires metric on which is being built be known up-front; ratios then depend size of (which could much larger than number terminals that arrive).We consider in least restrictive model not advance, but revealed parts along demand...

The online (uniform) buy-at-bulk network design problem asks us to a network, where the edge-costs exhibit economy-of-scale. Previous approaches this used tree-embeddings, giving randomized algorithms. Moreover, optimal results with logarithmic competitive ratio requires metric on which is being built be known up-front; ratios then depend size of (which could much larger than number terminals that arrive).We consider in least restrictive model not advance, but revealed parts along demand...

We give a general approach for solving optimization problems on noisy minor free and bounded treewidth graphs, where fraction of edges are adversarially corrupted. The setting was first considered by Magen Moharrami they gave (1 + ∊)-estimation algorithm the independent set problem. Later, Chan Har-Peled designed local search that finds ∊)-approximate set. However, nothing known regarding other in setting. Our main contribution is LP-based framework yields ∊)-approximation algorithms MAX-k-CSPs.

We consider the Max Unique Coverage problem, including applications to data stream model. The input is a universe of $n$ elements, collection $m$ subsets this universe, and cardinality constraint, $k$. goal select subcollection at most $k$ sets that maximizes unique coverage, i.e, number elements contained in exactly one selected sets. problem has wireless networks, radio broadcast, envy-free pricing. Our first main result fixed-parameter tractable approximation scheme (FPT-AS) for Coverage,...

The net frequency (NF) of a string, length $m$, in text, $n$, is the number occurrences string text with unique left and right extensions. Recently, Guo et al. [CPM 2024] showed that NF combinatorially interesting how two key questions can be computed efficiently offline setting. First, SINGLE-NF: reporting query an input text. Second, ALL-NF: occurrence each positive For many applications, however, facilitating these computations online manner highly desirable. We are first to solve above...

Probabilistic metric embedding into trees is a powerful technique for designing online algorithms. The standard approach to embed the entire underlying tree and then solve problem on latter. overhead in competitive ratio depends expected distortion of embedding, which logarithmic $n$, size metric. For many applications, such as network design problems, it natural ask if possible construct embeddings an fashion that would be polylogarithmic function $k$, number terminals. Our first main...

In this paper, we study the Dynamic Parameterized Subset Sampling (DPSS) problem in Word RAM model. DPSS, input is a set,~$S$, of~$n$ items, where each item,~$x$, has non-negative integer weight,~$w(x)$. Given pair of query parameters, $(\alpha, \beta)$, which rational number, parameterized subset sampling on~$S$ seeks to return $T \subseteq S$ such that item $x \in selected in~$T$, independently, with probability $p_x(\alpha, \beta) = \min \left\{\frac{w(x)}{\alpha \sum_{x\in S}...

In this paper, we study the Dynamic Parameterized Subset Sampling (DPSS) problem in Word RAM model. DPSS, input is a set, S , of n items, where each item, x has non-negative integer weight, w(x). Given pair query parameters, (α, β), which rational number, parameterized subset sampling on seeks to return T ⊆ such that item x∈ selected independently, with probability p_x(α, β) minimum between 1 and w(x) / (α \cdot W + total weight items . More specifically, DPSS defined dynamic setting, can be...

This paper tightens the best known analysis of Hein's 1989 algorithm to infer topology a weighted tree based on lengths paths between its leaves. It shows that number length queries required for degree-$k$ $n$ leaves is $O(n k \log_k n)$, which lower bound. also presents family trees performance asymptotically better, and no such exists competing n)$ algorithm.

The online joint replenishment problem (JRP) is a fundamental in the area of problems with delay. Over last decade, several works have studied generalizations JRP different cost functions for servicing requests. Most prior on and its focused clairvoyant setting. Recently, Touitou [Tou23a] developed non-clairvoyant framework that provided an $O(\sqrt{n \log n})$ upper bound wide class generalized JRP, where $n$ number request types. We advance study algorithms by providing simpler, modular...