Search for: All records

The multiple traveling salesman problem (mTSP) is an important variant of metric TSP where a set of k salespeople together visit a set of n cities while minimizing the total cost of the k routes under a given cost metric. The mTSP problem has applications to many real-life problems such as vehicle routing. Rothkopf [14] introduced another variant of TSP called many-visits TSP (MV-TSP) where a request r(v) is given for each city v and a single salesperson needs to visit each city r(v) times and return to his starting point. We note that in MV-TSP the cost of loops is positive, so a TSP solution cannot be trivially extended (without an increase in cost) to a MV-TSP solution by consecutively visiting each vertex to satisfy the visit requirements. A combination of mTSP and MV-TSP, called many-visits multiple TSP (MV-mTSP) was studied by Berczi, Mnich, and Vincze [3] where the authors give approximation algorithms for various variants of MV-mTSP. In this work, we show a simple linear programming (LP) based reduction that converts a mTSP LP-based algorithm to an LP-based algorithm for MV-mTSP with the same approximation factor. We apply this reduction to improve or match the current best approximation factors of several variants of the MV-mTSP. Our reduction shows that the addition of visit requests r(v) to mTSP does not make the problem harder to approximate even when r(v) is exponential in the number of vertices. To apply our reduction, we either use existing LP-based algorithms for mTSP variants or show that several existing combinatorial algorithms for mTSP variants can be interpreted as LP-based algorithms. This allows us to apply our reduction to these combinatorial algorithms while achieving improved guarantees. 

In optimal experimental design, the objective is to select a limited set of experiments that maximizes information about unknown model parameters based on factor levels. This work addresses the generalized D-optimal design problem, allowing for nonlinear relationships in factor levels. We develop scalable algorithms suitable for cases where the number of candidate experiments grows exponentially with the factor dimension, focusing on both first- and second-order models under design constraints. Particularly, our approach integrates convex relaxation with pricing-based local search techniques, which can provide upper bounds and performance guarantees. Unlike traditional local search methods, such as the ``Fedorov exchange" and its variants, our method effectively accommodates arbitrary side constraints in the design space. Furthermore, it yields both a feasible solution and an upper bound on the optimal value derived from the convex relaxation. Numerical results highlight the efficiency and scalability of our algorithms, demonstrating superior performance compared to the state-of-the-art commercial software, \texttt{JMP}. 

We study the complexity of sampling, rounding, and integrating arbitrary logconcave functions given an evaluation oracle. Our new approach provides the first complexity improvements in nearly two decades for general logconcave functions for all three problems, and matches the best-known complexities for the special case of uniform distributions on convex bodies. For the sampling problem, our output guarantees are significantly stronger than previously known, and lead to a streamlined analysis of statistical estimation based on dependent random samples. 

In online sales, sellers usually offer each potential buyer a posted price in a take-it-or-leave fashion. Buyers can sometimes see posted prices faced by other buyers, and changing the price frequently could be considered unfair. The literature on posted-price mechanisms and prophet inequality problems has studied the two extremes of pricing policies, the fixed-price policy and fully dynamic pricing. The former is suboptimal in revenue but is perceived as fairer than the latter. This work examines the middle situation, where there are at most k distinct prices over the selling horizon. Using the framework of prophet inequalities with independent and identically distributed random variables, we propose a new prophet inequality for strategies that use at most k thresholds. We present asymptotic results in k and results for small values of k. For k = 2 prices, we show an improvement of at least 11% over the best fixed-price solution. Moreover, k = 5 prices suffice to guarantee almost 99% of the approximation factor obtained by a fully dynamic policy that uses an arbitrary number of prices. From a technical standpoint, we use an infinite-dimensional linear program in our analysis; this formulation could be of independent interest to other online selection problems. 

Motivated by fairness concerns, we study existence and computation of portfolios, defined as: given anoptimization problem with feasible solutions D, a class C of fairness objective functions, a set X of feasible solutions is an α-approximate portfolio if for each objective f in C, there is an α-approximation for f in X. We study the trade-off between the size |X| of the portfolio and its approximation factor αfor various combinatorial problems, such as scheduling, covering, and facility location, and choices of C as top-k, ordered and symmetric monotonic norms. Our results include: (i) an α-approximate portfolio of size O(log d*log(α/4))for ordered norms and lower bounds of size \Omega( log dlog α+log log d)for the problem of scheduling identical jobs on d unidentical machines, (ii) O(log n)-approximate O(log n)-sized portfolios for facility location on n points for symmetric monotonic norms, and (iii) logO(d)^(r^2)-size O(1)-approximate portfolios for ordered norms and O(log d)-approximate for symmetric monotonic norms for covering polyhedra with a constant rnumber of constraints. The latter result uses our novel OrderAndCount framework that obtains an exponentialimprovement in portfolio sizes compared to current state-of-the-art, which may be of independent interest. 

We present a new random walk for uniformly sampling high-dimensional convex bodies. It achieves state-of-the-art runtime complexity with stronger guarantees on the output than previously known, namely in Rényi divergence (which implies TV, KL etc.). The proof departs from known approaches for polytime algorithms for the problem - we utilize a stochastic diffusion perspective to show contraction to the target distribution with the rate of convergence determined by functional isoperimetric constants of the stationary density. 

In the minimum eigenvalue problem, we are given a collection of vectors and the goal is to pick a subset B to maximize the minimum eigenvalue of the matrix formed by the sum of their outer products. We give a -time randomized algorithm that finds an assignment subject to a partition constraint whose minimum eigenvalue is at least $$1-\epsilon$$ times the optimum, with high probability. As a byproduct, we also get a simple algorithm for an algorithmic version of Kadison-Singer problem. 

Online advertising has motivated interest in online selection problems. Displaying ads to the right users benefits both the platform (e.g., via pay-per-click) and the advertisers (by increasing their reach). In practice, not all users click on displayed ads, while the platform’s algorithm may miss the users most disposed to do so. This mismatch decreases the platform’s revenue and the advertiser’s chances to reach the right customers. With this motivation, we propose a secretary problem where a candidate may or may not accept an offer according to a known probability p. Because we do not know the top candidate willing to accept an offer, the goal is to maximize a robust objective defined as the minimum over integers k of the probability of choosing one of the top k candidates, given that one of these candidates will accept an offer. Using Markov decision process theory, we derive a linear program for this max-min objective whose solution encodes an optimal policy. The derivation may be of independent interest, as it is generalizable and can be used to obtain linear programs for many online selection models. We further relax this linear program into an infinite counterpart, which we use to provide bounds for the objective and closed-form policies. For [Formula: see text], an optimal policy is a simple threshold rule that observes the first [Formula: see text] fraction of candidates and subsequently makes offers to the best candidate observed so far. Funding: Financial support from the U.S. National Science Foundation [Grants CCF-2106444, CCF-1910423, and CMMI 1552479] is gratefully acknowledged. 

The connections between (convex) optimization and (logconcave) sampling have been considerably enriched in the past decade with many conceptual and mathematical analogies. For instance, the Langevin algorithm can be viewed as a sampling analogue of gradient descent and has condition-number-dependent guarantees on its performance. In the early 1990s, Nesterov and Nemirovski developed the Interior-Point Method (IPM) for convex optimization based on self-concordant barriers, providing efficient algorithms for structured convex optimization, often faster than the general method. This raises the following question: can we develop an analogous IPM for structured sampling problems? In 2012, Kannan and Narayanan proposed the Dikin walk for uniformly sampling polytopes, and an improved analysis was given in 2020 by Laddha-Lee-Vempala. The Dikin walk uses a local metric defined by a self-concordant barrier for linear constraints. Here we generalize this approach by developing and adapting IPM machinery together with the Dikin walk for poly-time sampling algorithms. Our IPM-based sampling framework provides an efficient warm start and goes beyond uniform distributions and linear constraints. We illustrate the approach on important special cases, in particular giving the fastest algorithms to sample uniform, exponential, or Gaussian distributions on a truncated PSD cone. The framework is general and can be applied to other sampling algorithms. 

Recent language models generate false but plausible-sounding text with surprising frequency. Such “hallucinations” are an obstacle to the usability of language-based AI systems and can harm people who rely upon their outputs. This work shows that there is an inherent statistical lower-bound on the rate that pretrained language models hallucinate certain types of facts, having nothing to do with the transformer LM architecture or data quality. For “arbitrary” facts whose veracity cannot be determined from the training data, we show that hallucinations must occur at a certain rate for language models that satisfy a statistical calibration condition appropriate for generative language models. Specifically, if the maximum probability of any fact is bounded, we show that the probability of generating a hallucination is close to the fraction of facts that occur exactly once in the training data (a “Good-Turing” estimate), even assuming ideal training data without errors. One conclusion is that models pretrained to be sufficiently good predictors (i.e., calibrated) may require post-training to mitigate hallucinations on the type of arbitrary facts that tend to appear once in the training set. However, our analysis also suggests that there is no statistical reason that pretraining will lead to hallucination on facts that tend to appear more than once in the training data (like references to publications such as articles and books, whose hallucinations have been particularly notable and problematic) or on systematic facts (like arithmetic calculations). Therefore, different architectures and learning algorithms may mitigate these latter types of hallucinations.