An official website of the United States government
In this paper, we propose a general framework to design efficient polynomial-time approximation schemes (EPTASs) for fundamental stochastic combinatorial optimization problems. Technically speaking, our approach relies on presenting tailor-made reductions to a newly introduced multidimensional Santa Claus problem. Even though the single-dimensional version of this problem is already known to be APX-Hard, we prove that an EPTAS can be designed for a constant number of machines and dimensions, which hold for each of our applications. To demonstrate the versatility of our framework, we first study selection-stopping settings to derive an EPTAS for the free-order prophets problem and for its cost-driven generalization, Pandora’s box with commitment. These results constitute the first approximation schemes in the nonadaptive setting and improve on known inefficient polynomial-time approximation schemes (PTASs) for their adaptive variants. Next, turning our attention to stochastic probing problems, we obtain an EPTAS for the adaptive ProbeMax problem as well as for its nonadaptive counterpart. In both cases, state-of-the-art approximability results have been inefficient PTASs (Chen et al. [25], Fu et al. [35]). Funding: This work was supported by the National Science Foundation, Division of Computing and Communication Foundations [Grants 2327010 and 2440113].
more »
« less
This content will become publicly available on July 1, 2026
Nonadaptive Stochastic Score Classification and Explainable Half-Space Evaluation
Nonadaptive Stochastic Score Classification Sequential testing problems involve a system with several components, each of which is working with some independent probability. The working/failed status of each component can be determined by performing a test, which is usually expensive. So, the goal is to perform tests in a carefully chosen sequence until the overall system status can be evaluated. These problems arise in a variety of applications, such as healthcare, manufacturing, and telecommunication. A common task in these applications is to categorize the system into one of several classes that correspond to the system status being poor, fair, good, excellent, etc. In “Nonadaptive Stochastic Score Classification and Explainable Half-Space Evaluation,” Ghuge, Gupta, and Nagarajan provide the first constant-factor approximation algorithm for this problem. Moreover, the resulting policy is nonadaptive, which results in significant savings in computational time. The authors also validate their theoretical results via computational experiments, where they observe that their algorithm’s cost is on average at most 50% more than an information-theoretic lower bound.
more »
« less
- PAR ID:
- 10631736
- Publisher / Repository:
- INFORMS
- Date Published:
- Journal Name:
- Operations Research
- Volume:
- 73
- Issue:
- 4
- ISSN:
- 0030-364X
- Page Range / eLocation ID:
- 2204 to 2222
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Supervised machine learning techniques have proven to be effective tools for engineering design exploration and optimization applications, in which they are especially useful for mapping promising or feasible regions of the design space. The design space mappings can be used to inform early-stage design exploration, provide reliability assessments, and aid convergence in multiobjective or multilevel problems that require collaborative design teams. However, the accuracy of the mappings can vary based on problem factors such as the number of design variables, presence of discrete variables, multimodality of the underlying response function, and amount of training data available. Additionally, there are several useful machine learning algorithms available, and each has its own set of algorithmic hyperparameters that significantly affect accuracy and computational expense. This work elucidates the use of machine learning for engineering design exploration and optimization problems by investigating the performance of popular classification algorithms on a variety of example engineering optimization problems. The results are synthesized into a set of observations to provide engineers with intuition for applying these techniques to their own problems in the future, as well as recommendations based on problem type to aid engineers in algorithm selection and utilization.more » « less
-
null (Ed.)Discrete dynamical systems serve as useful formal models to study diffusion phenomena in social networks. Motivated by applications in systems biology, several recent papers have studied algorithmic and complexity aspects of diffusion problems for dynamical systems whose underlying graphs are directed, and may contain directed cycles. Such problems can be regarded as reachability problems in the phase space of the corresponding dynamical system. We show that computational intractability results for reachability problems hold even for dynamical systems on directed acyclic graphs (dags). We also show that for dynamical systems on dags where each local function is monotone, the reachability problem can be solved efficiently.more » « less
-
In recent years, federated minimax optimization has attracted growing interest due to its extensive applications in various machine learning tasks. While Smoothed Alternative Gradient Descent Ascent (Smoothed-AGDA) has proved successful in centralized nonconvex minimax optimization, how and whether smoothing techniques could be helpful in a federated setting remains unexplored. In this paper, we propose a new algorithm termed Federated Stochastic Smoothed Gradient Descent Ascent (FESS-GDA), which utilizes the smoothing technique for federated minimax optimization. We prove that FESS-GDA can be uniformly applied to solve several classes of federated minimax problems and prove new or better analytical convergence results for these settings. We showcase the practical efficiency of FESS-GDA in practical federated learning tasks of training generative adversarial networks (GANs) and fair classification.more » « less
-
We introduce a novel criterion in clustering that seeks clusters with limitedrangeof values associated with each cluster's elements. In clustering or classification the objective is to partition a set of objects into subsets, called clusters or classes, consisting of similar objects so that different clusters are as dissimilar as possible. We propose a number of objective functions that employ the range of the clusters as part of the objective function. Several of the proposed objectives mimic objectives based on sums of similarities. These objective functions are motivated by image segmentation problems, where the diameter, or range of values associated with objects in each cluster, should be small. It is demonstrated that range‐based problems are in general easier, in terms of their complexity, than the analogous similarity‐sum problems. Several of the problems we present could therefore be viable alternatives to existing clustering problems which are NP‐hard, offering the advantage of efficient algorithms.more » « less
