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 August 26, 2025

We study the design of embeddings into Euclidean space with outliers. Given a metric space (X, d) and aninteger k, the goal is to embed all but k points in X (called the “outliers”) into ℓ2 with the smallest possibledistortion c. Finding the optimal distortion c for a given outlier set size k, or alternately the smallest k fora given target distortion c are both NPhard problems. In fact, it is UGChard to approximate k to withina factor smaller than 2 even when the metric sans outliers is isometrically embeddable into ℓ2. We considerbicriteria approximations. Our main result is a polynomial time algorithm that approximates the outlier setsize to within an O(log2 k) factor and the distortion to within a constant factor.The main technical component in our result is an approach for constructing Lipschitz extensions ofembeddings into Banach spaces (such as ℓp spaces). We consider a stronger version of Lipschitz extensionthat we call a nested composition of embeddings: given a low distortion embedding of a subset S of the metricspace X, our goal is to extend this embedding to all of X such that the distortion over S is preserved, whereasthe distortion over the remaining pairs of points in X is bounded by a function of the size of X \ S. Priorwork on Lipschitz extension considers settings where the size of X is potentially much larger than that of Sand the expansion bounds depend on S. In our setting, the set S is nearly all of X and the remaining setX \ S, a.k.a. the outliers, is small. We achieve an expansion bound that is polylogarithmic in X \ S.more » « lessFree, publiclyaccessible full text available January 7, 2025

Characterizing the Efficiency of Static Pricing Schemes as a Function of the Supply
The problem of selling a supply of k units to a stream of customers constitutes one of the cornerstones in revenue management. Static pricing schemes (that output the same price to all customers) are commonly used because of their simplicity and their many desirable properties; they are anonymous, nonadaptive, and order oblivious. Although the efficiency of those schemes should improve as the supply k increases, prior work has only focused either on algorithms that aim for a constant approximation that is independent of k or on the setting where k becomes really large. In contrast, this paper characterizes the efficiency of static pricing schemes as a function of the supply. Our approach stems from identifying a “sweet spot” between selling enough items and obtaining enough utility from customers with high valuations. Subsequent work shows that our pricing scheme is the optimal static pricing for every value of k.

Megow, Nicole ; Smith, Adam (Ed.)We revisit the classic Pandora’s Box (PB) problem under correlated distributions on the box values. Recent work of [Shuchi Chawla et al., 2020] obtained constant approximate algorithms for a restricted class of policies for the problem that visit boxes in a fixed order. In this work, we study the complexity of approximating the optimal policy which may adaptively choose which box to visit next based on the values seen so far. Our main result establishes an approximationpreserving equivalence of PB to the well studied Uniform Decision Tree (UDT) problem from stochastic optimization and a variant of the MinSum Set Cover (MSSC_f) problem. For distributions of support m, UDT admits a log m approximation, and while a constant factor approximation in polynomial time is a longstanding open problem, constant factor approximations are achievable in subexponential time [Ray Li et al., 2020]. Our main result implies that the same properties hold for PB and MSSC_f. We also study the case where the distribution over values is given more succinctly as a mixture of m product distributions. This problem is again related to a noisy variant of the Optimal Decision Tree which is significantly more challenging. We give a constantfactor approximation that runs in time n^Õ(m²/ε²) when the mixture components on every box are either identical or separated in TV distance by ε.more » « less

We design fairsponsored search auctions that achieve a nearoptimal tradeoff between fairness and quality. Our work builds upon the model and auction design of Chawla and Jagadeesan, who considered the special case of a single slot. We consider sponsored search settings with multiple slots and the standard model of clickthrough rates that are multiplicatively separable into an advertiserspecific component and a slotspecific component. When similar users have similar advertiserspecific clickthrough rates, our auctions achieve the same nearoptimal tradeoff between fairness and quality. When similar users can have different advertiserspecific preferences, we show that a preferencebased fairness guarantee holds. Finally, we provide a computationally efficient algorithm for computing payments for our auctions as well as those in previous work, resolving another open direction from Chawla and Jagadeesan.more » « less

We design fairsponsored search auctions that achieve a nearoptimal tradeoff between fairness and quality. Our work builds upon the model and auction design of Chawla and Jagadeesan, who considered the special case of a single slot. We consider sponsored search settings with multiple slots and the standard model of clickthrough rates that are multiplicatively separable into an advertiserspecific component and a slotspecific component. When similar users have similar advertiserspecific clickthrough rates, our auctions achieve the same nearoptimal tradeoff between fairness and quality. When similar users can have different advertiserspecific preferences, we show that a preferencebased fairness guarantee holds. Finally, we provide a computationally efficient algorithm for computing payments for our auctions as well as those in previous work, resolving another open direction from Chawla and Jagadeesan.more » « less

We study the revenue guarantees and approximability of item pricing. Recent work shows that with n heterogeneous items, itempricing guarantees an O(logn) approximation to the optimal revenue achievable by any (buymany) mechanism, even when buyers have arbitrarily combinatorial valuations. However, finding good item prices is challenging – it is known that even under unitdemand valuations, it is NPhard to find item prices that approximate the revenue of the optimal item pricing better than O(√n). Our work provides a more finegrained analysis of the revenue guarantees and computational complexity in terms of the number of item “categories” which may be significantly fewer than n. We assume the items are partitioned in k categories so that items within a category are totallyordered and a buyer’s value for a bundle depends only on the best item contained from every category. We show that itempricing guarantees an O(logk) approximation to the optimal (buymany) revenue and provide a PTAS for computing the optimal itempricing when k is constant. We also provide a matching lower bound showing that the problem is (strongly) NPhard even when k=1. Our results naturally extend to the case where items are only partially ordered, in which case the revenue guarantees and computational complexity depend on the width of the partial ordering, i.e. the largest set for which no two items are comparable.more » « less