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.

We give nearoptimal algorithms for computing an ellipsoidal rounding of a convex polytope whose vertices are given in a stream. The approximation factor is linear in the dimension (as in John's theorem) and only loses an excess logarithmic factor in the aspect ratio of the polytope. Our algorithms are nearly optimal in two senses: first, their runtimes nearly match those of the most efficient known algorithms for the offline version of the problem. Second, their approximation factors nearly match a lower bound we show against a natural class of geometric streaming algorithms. In contrast to existing works in the streaming setting that compute ellipsoidal roundings only for centrally symmetric convex polytopes, our algorithms apply to general convex polytopes. We also show how to use our algorithms to construct coresets from a stream of points that approximately preserve both the ellipsoidal rounding and the convex hull of the original set of points.more » « lessFree, publiclyaccessible full text available June 11, 2025

We prove a new generalization of the higherorder Cheeger inequality for partitioning with buffers. Consider a graph G = (V, E). The buffered expansion of a set S ⊆ V with a buffer B ⊆ V∖S is the edge expansion of S after removing all the edges from set S to its buffer B. An εbuffered kpartitioning is a partitioning of a graph into disjoint components P_i and buffers B_i, in which the size of buffer B_i for P_i is small relative to the size of P_i: B_i ≤ εP_i. The buffered expansion of a buffered partition is the maximum of buffered expansions of the k sets P_i with buffers B_i. Let h^{k,ε}_G be the buffered expansion of the optimal εbuffered kpartitioning, then for every δ>0, h^{k,ε}_G ≤ O(1)⋅(log k) ⋅λ_{⌊(1+δ)k⌋} / ε, where λ_{⌊(1+δ)k⌋} is the ⌊(1+δ)k⌋th smallest eigenvalue of the normalized Laplacian of G. Our inequality is constructive and avoids the ``squareroot loss'' that is present in the standard Cheeger inequalities (even for k=2). We also provide a complementary lower bound, and a novel generalization to the setting with arbitrary vertex weights and edge costs. Moreover our result implies and generalizes the standard higherorder Cheeger inequalities and another recent Cheegertype inequality by Kwok, Lau, and Lee (2017) involving robust vertex expansion.more » « lessFree, publiclyaccessible full text available January 1, 2025

We introduce a framework for performing vectorvalued regression in finitedimensional Hilbert spaces. Using Lipschitz smoothness as our regularizer, we leverage Kirszbraun’s extension theorem for offdata prediction. We analyze the statistical and computational aspects of this method—to our knowledge, its first application to supervised learning. We decompose this task into two stages: training (which corresponds operationally to smoothing/regularization) and prediction (which is achieved via Kirszbraun extension). Both are solved algorithmically via a novel multiplicative weight updates (MWU) scheme, which, for our problem formulation, achieves significant runtime speedups over generic interior point methods. Our empirical results indicate a dramatic advantage over standard offtheshelf solvers in our regression setting.more » « lessFree, publiclyaccessible full text available December 7, 2024

Megow, Nicole ; Smith, Adam (Ed.)We provide new approximation algorithms for the RedBlue Set Cover and Circuit Minimum Monotone Satisfying Assignment (MMSA) problems. Our algorithm for RedBlue Set Cover achieves Õ(m^{1/3})approximation improving on the Õ(m^{1/2})approximation due to Elkin and Peleg (where m is the number of sets). Our approximation algorithm for MMSA_t (for circuits of depth t) gives an Õ(N^{1δ}) approximation for δ = 1/3 2^{3⌈t/2⌉}, where N is the number of gates and variables. No nontrivial approximation algorithms for MMSA_t with t ≥ 4 were previously known. We complement these results with lower bounds for these problems: For RedBlue Set Cover, we provide a nearly approximation preserving reduction from Min kUnion that gives an Ω(m^{1/4  ε}) hardness under the DensevsRandom conjecture, while for MMSA we sketch a proof that an SDP relaxation strengthened by SheraliAdams has an integrality gap of N^{1ε} where ε → 0 as the circuit depth t → ∞.more » « less

Gørtz, Inge Li ; FarachColton, Martin ; Puglisi, Simon J ; Herman, Grzegorz (Ed.)We consider variants of the classic Multiway Cut problem. Multiway Cut asks to partition a graph G into k parts so as to separate k given terminals. Recently, Chandrasekaran and Wang (ESA 2021) introduced l_pnorm Multiway Cut, a generalization of the problem, in which the goal is to minimize the l_p norm of the edge boundaries of k parts. We provide an O(log^{1/2} n log^{1/2 + 1/p} k) approximation algorithm for this problem, improving upon the approximation guarantee of O(log^{3/2} n log^{1/2} k) due to Chandrasekaran and Wang. We also introduce and study Norm Multiway Cut, a further generalization of Multiway Cut. We assume that we are given access to an oracle, which answers certain queries about the norm. We present an O(log^{1/2} n log^{7/2} k) approximation algorithm with a weaker oracle and an O(log^{1/2} n log^{5/2} k) approximation algorithm with a stronger oracle. Additionally, we show that without any oracle access, there is no n^{1/4ε} approximation algorithm for every ε > 0 assuming the Hypergraph DensevsRandom Conjecture.more » « less

Social science approaches to missing values predict avoided, unrequested, or lost information from dense data sets, typically surveys. The authors propose a matrix factorization approach to missing data imputation that (1) identifies underlying factors to model similarities across respondents and responses and (2) regularizes across factors to reduce their overinfluence for optimal data reconstruction. This approach may enable social scientists to draw new conclusions from sparse data sets with a large number of features, for example, historical or archival sources, online surveys with high attrition rates, or data sets created from Web scraping, which confound traditional imputation techniques. The authors introduce matrix factorization techniques and detail their probabilistic interpretation, and they demonstrate these techniques’ consistency with Rubin’s multiple imputation framework. The authors show via simulations using artificial data and data from realworld subsets of the General Social Survey and National Longitudinal Study of Youth cases for which matrix factorization techniques may be preferred. These findings recommend the use of matrix factorization for data reconstruction in several settings, particularly when data are Boolean and categorical and when large proportions of the data are missing.

We study the problem of fair kmedian where each cluster is required to have a fair representation of individuals from different groups. In the fair representation kmedian problem, we are given a set of points X in a metric space. Each point x ∈ X belongs to one of ℓ groups. Further, we are given fair representation parameters αj and β_j for each group j ∈ [ℓ]. We say that a kclustering C_1, ⋅⋅⋅, C_k fairly represents all groups if the number of points from group j in cluster C_i is between α_j C_i and β_j C_i for every j ∈ [ℓ] and i ∈ [k]. The goal is to find a set of k centers and an assignment such that the clustering defined by fairly represents all groups and minimizes the ℓ_1objective ∑_{x ∈ X} d(x, ϕ(x)). We present an O(log k)approximation algorithm that runs in time n^{O(ℓ)}. Note that the known algorithms for the problem either (i) violate the fairness constraints by an additive term or (ii) run in time that is exponential in both k and ℓ. We also consider an important special case of the problem where and for all j ∈ [ℓ]. For this special case, we present an O(log k)approximation algorithm that runs in time.more » « less