Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

Free, publiclyaccessible full text available June 20, 2023

Free, publiclyaccessible full text available January 1, 2023

Free, publiclyaccessible full text available January 1, 2023

We consider nodeweighted survivable network design (SNDP) in planar graphs and minorclosed families of graphs. The input consists of a nodeweighted undirected graph G = ( V , E ) and integer connectivity requirements r ( uv ) for each unordered pair of nodes uv . The goal is to find a minimum weighted subgraph H of G such that H contains r ( uv ) disjoint paths between u and v for each node pair uv . Three versions of the problem are edgeconnectivity SNDP (ECSNDP), elementconnectivity SNDP (ElemSNDP), and vertexconnectivity SNDP (VCSNDP), depending on whether the paths are required to be edge, element, or vertex disjoint, respectively. Our main result is an O ( k )approximation algorithm for ECSNDP and ElemSNDP when the input graph is planar or more generally if it belongs to a proper minorclosed family of graphs; here, k = max uv r ( uv ) is the maximum connectivity requirement. This improves upon the O ( k log n )approximation known for nodeweighted ECSNDP and ElemSNDP in general graphs [31]. We also obtain an O (1) approximation for nodeweighted VCSNDP when the connectivity requirements are in {0, 1, 2}; for higher connectivity our resultmore »

Belkin, Mikhail ; Kpotufe, Samor (Ed.)We present an $e^{O(p)} (\log \ell) / (\log \log \ell)$approximation algorithm for socially fair clustering with the $\ell_p$objective. In this problem, we are given a set of points in a metric space. Each point belongs to one (or several) of $\ell$ groups. The goal is to find a $k$medians, $k$means, or, more generally, $\ell_p$clustering that is simultaneously good for all of the groups. More precisely, we need to find a set of $k$ centers $C$ so as to minimize the maximum over all groups $j$ of $\sum_{u \text{ in group } j} d(u, C)^p$. The socially fair clustering problem was independently proposed by Abbasi, Bhaskara, and Venkatasubramanian (2021) and Ghadiri, Samadi, and Vempala (2021). Our algorithm improves and generalizes their $O(\ell)$approximation algorithms for the problem. The natural LP relaxation for the problem has an integrality gap of $\Omega(\ell)$. In order to obtain our result, we introduce a strengthened LP relaxation and show that it has an integrality gap of $\Theta((\log \ell) / (\log \log \ell))$ for a fixed p. Additionally, we present a bicriteria approximation algorithm, which generalizes the bicriteria approximation of Abbasi et al. (2021).

A graph spanner is a fundamental graph structure that faithfully preserves the pairwise distances in the input graph up to a small multiplicative stretch. The common objective in the computation of spanners is to achieve the bestknown existential sizestretch tradeoff efficiently. Classical models and algorithmic analysis of graph spanners essentially assume that the algorithm can read the input graph, construct the desired spanner, and write the answer to the output tape. However, when considering massive graphs containing millions or even billions of nodes not only the input graph, but also the output spanner might be too large for a single processor to store. To tackle this challenge, we initiate the study of local computation algorithms (LCAs) for graph spanners in general graphs, where the algorithm should locally decide whether a given edge (u,v)∈E belongs to the output spanner. Such LCAs give the user the `illusion' that a specific sparse spanner for the graph is maintained, without ever fully computing it. We present the following results: For general nvertex graphs and r∈{2,3}, there exists an LCA for (2r−1)spanners with O˜(n1+1/r) edges and sublinear probe complexity of O˜(n1−1/2r). These size/stretch tradeoffs are best possible (up to polylogarithmic factors). For every k≥1 andmore »