optimality bounds – Optimization Online

A Generalized Polynomial Lower Bound for the Weighted Completion Time Variance in a Single Machine

Published: 2026/10/04

Approximation Algorithms, Combinatorial Optimization, Scheduling optimality bounds, scheduling, single-machine, Weighted completion time variance

This paper studies the single-machine problem of minimizing the weighted completion time variance (WCTV) and proposes a polynomially computable lower-bounding framework that generalizes the benchmark introduced by Nessah and Chu (2010). We first develop a generalized augmented-sequence decomposition that mathematically connects the weighted problem with the classical unweighted variance setting. Using this decomposition, we derive … Read more

Validation Analysis of Robust Stochastic Approximation Method

Published: 2008/05/20, Updated: 2009/05/25

Stochastic Programming asset allocation problem, conditional-value-at-risk, large deviations estimates, mirror descent algorithm, monte carlo sampling, optimality bounds, prox mapping, sample average approximation method, stochastic approximation, stochastic programming

The main goal of this paper is to develop accuracy estimates for stochastic programming problems by employing robust stochastic approximation (SA) type algorithms. To this end we show that while running a Robust Mirror Descent Stochastic Approximation procedure one can compute, with a small additional effort, lower and upper statistical bounds for the optimal objective … Read more