Solves highly intractable (#P-hard) multi-objective optimization problems with tight approximation guarantees using a novel SAT-oracle approach.
April 2, 2026
Original Paper
Approximating Pareto Frontiers in Stochastic Multi-Objective Optimization via Hashing and Randomization
arXiv · 2604.01098
The Takeaway
Stochastic Multi-Objective Optimization is usually computationally prohibitive for real-world complexity; this method provides a scalable way to find near-optimal Pareto frontiers in uncertain environments like supply chains and road networks.
From the abstract
Stochastic Multi-Objective Optimization (SMOO) is critical for decision-making trading off multiple potentially conflicting objectives in uncertain environments. SMOO aims at identifying the Pareto frontier, which contains all mutually non-dominating decisions. The problem is highly intractable due to the embedded probabilistic inference, such as computing the marginal, posterior probabilities, or expectations. Existing methods, such as scalarization, sample average approximation, and evolutiona