Search

Given a metric space \scrM = (X, γ), a weighted graph G over X is a metric t-spanner of scrM if for every u, v \in X, γ(u, v) \leq γG(u, v) \leq t \cdot γ (u, v), where γ G is the shortest path metric in G. In this paper, we construct spanners for finite sets in metric spaces in the online setting. Here, we are given a sequence of points (s1,. . ., sn), where the points are presented one at a time (i.e., after i steps, we see Si = \{ s1, . . ., si\}). The algorithm is allowed to add edges to the spanner when a new point arrives; however, it is not allowed to remove any edge from the spanner. The goal is to maintain a t-spanner Gi for Si for all i, while minimizing the number of edges, and their total weight. We construct online (1+ε)-spanners in the Euclidean d-space, (2k 1)(1+ε)-spanners for general metrics, and (2 + ε)-spanners for ultrametrics. Most notably, in the Euclidean plane, we construct a (1 + ε)-spanner with competitive ratio O(\varepsilon 3/2 log n 1 log n), bypassing the classic lower bound (ε 2) for lightness, which compares the weight of the spanner to that of the minimum spanning tree. [ABSTRACT FROM AUTHOR]

Since the seminal result of Karger, Motwani, and Sudan, algorithms for approximate 3-coloring have primarily centered around rounding the solution to a Semidefinite Program. However, it is likely that important combinatorial or algebraic insights are needed in order to break the no(1) threshold. One way to develop new understanding in graph coloring is to study special subclasses of graphs. For instance, Blum studied the 3-coloring of random graphs, and Arora and Ge studied the 3-coloring of graphs with low threshold-rank. In this work, we study graphs that arise from a tensor product, which appear to be novel instances of the 3-coloring problem. We consider graphs of the form H = (V,E) with V = V (K3 G) and E = E(K3 G) s E, where E E(K3 G) is any edge set such that no vertex has more than an -fraction of its edges in E. We show that one can construct H = K3 \times G with V (H) = V (H) that is close to H. For arbitrary G, H satisfies | E(H)Δ E H)| O(\epsilon | E(H)|). Additionally, when G is a mild expander, we provide a 3-coloring for H in polynomial time. These results partially generalize an exact tensor factorization algorithm of Imrich. On the other hand, without any assumptions on G, we show that it is NP-hard to 3-color H. [ABSTRACT FROM AUTHOR]

Let P be a set of points in Rd, where each point p ∈ P has an associated transmission range, denoted (p). The range assignment induces a directed communication graph Gp (P) on P, which contains an edge (p, q) iff | pq| (p). In the broadcast range-assignment problem, the goal is to assign the ranges such that (P) contains an arborescence rooted at a designated root node and the costΣp∈ P(p)² of the assignment is minimized. We study the dynamic version of this problem. In particular, we study trade-offs between the stability of the solution-the number of ranges that are modified when a point is inserted into or deleted from P-and its approximation ratio. To this end we study k-stable algorithms, which are algorithms that modify the range of at most k points when they update the solution. We also introduce the concept of a stable approximation scheme, or SAS for short. A SAS is an update algorithm \mathrm{A}\mathrm{L}\mathrm{G} that, for any given fixed parameter ε >0, is kε-stable and that maintains a solution with approximation ratio 1 + \ε, where the stability parameter k(\varepsilon) only depends on ε and not on the size of P. We study such trade-offs in three settings. (1) For the problem in R¹, we present a SAS with kε = O(1/ε. Furthermore, we prove that this is tight in the worst case: any SAS for the problem must have kε =ε (1ε). We also present 1-, 2-, and 3-stable algorithms with constant approximation ratio. (2) For the problem in S1 (that is, when the underlying space is a circle) we prove that no SAS exists. This is in spite of the fact that, for the static problem in S1, we prove that an optimal solution can always be obtained by cutting the circle at an appropriate point and solving the resulting problem in R¹. (3) For the problem in R2, we also prove that no SAS exists, and we present a O(1)-stable O(1)-approximation algorithm. Most results γ generalize to the setting where, for any given constant α > 1, the range-assignment cost is pΣ (p)∈α. [ABSTRACT FROM AUTHOR]

We consider classes of objective functions of cardinality-constrained maximization problems for which the greedy algorithm guarantees a constant approximation. We propose the new class of γ -β -augmentable functions and prove that it encompasses several important subclasses, such as functions of bounded submodularity ratio, \alpha -augmentable functions, and weighted rank functions of an independence system of bounded rank quotient-as well as additional objective functions for which the greedy algorithm yields an approximation. For this general class of functions, we show a tight bound of α/γeα/eα-1 \mathrm{e}α 1 on the approximation ratio of the greedy algorithm that tightly interpolates between bounds from the literature for functions of bounded submodularity ratio and for α -augmentable functions. In particular, as a by-product, we close a gap in [A. Bernstein et al., Math. Program., 191 (2022), pp. 953--979] by obtaining a tight lower bound for \alpha -augmentable functions for all \α 1. For weighted rank functions of independence systems, our tight bound becomes α, which recovers the known bound of 1/q for independence systems of rank quotient at least q. [ABSTRACT FROM AUTHOR]

We consider a selection problem with stochastic probing. There is a set of items whose values are drawn from independent distributions. The distributions are known in advance. Each item can be tested repeatedly. Each test reduces the uncertainty about the realization of its value. We study a testing model, where the first test reveals whether the realized value is smaller or larger than the c-quantile of the underlying distribution of some constant c \in (0, 1). Subsequent tests allow us to further narrow down the interval in which the realization is located. There is a limited number of possible tests, and our goal is to design near-optimal testing strategies that allow us to maximize the expected value of the chosen item. We study both identical and nonidentical distributions and develop polynomial-time algorithms with constant approximation factors in both scenarios. [ABSTRACT FROM AUTHOR]