"Non UBC"@en .
"DSpace"@en .
"El Housni, Omar"@en .
"2019-07-15T08:32:35Z"@en .
"2019-01-15T11:01"@en .
"We study the performance of affine policies for two-stage adjustable robust optimization problem under a budget of uncertainty set. This important class of uncertainty sets provides the flexibility to adjust the level of conservatism in terms of probabilistic bounds on constraint violations. The two-stage adjustable robust optimization problem is hard to approximate within a factor better than $\Omega( \frac{\log n}{\log \log n})$ for budget of uncertainty sets where $n$ is the number of decision variables. We show that surprisingly affine policies provide the optimal approximation for this class of uncertainty sets that matches the hardness of approximation; thereby, further confirming the power of affine policies. We also present strong theoretical guarantees for affine policies when the uncertainty set is given by intersection of budget constraints. Furthermore, our analysis gives a significantly faster algorithm to compute near-optimal affine policies. This is joint work with Vineet Goyal."@en .
"https://circle.library.ubc.ca/rest/handle/2429/70979?expand=metadata"@en .
"38.0"@en .
"video/mp4"@en .
""@en .
"Author affiliation: Columbia University"@en .
"Banff (Alta.)"@en .
"10.14288/1.0379833"@en .
"eng"@en .
"Unreviewed"@en .
"Vancouver : University of British Columbia Library"@en .
"Banff International Research Station for Mathematical Innovation and Discovery"@en .
"Attribution-NonCommercial-NoDerivatives 4.0 International"@en .
"http://creativecommons.org/licenses/by-nc-nd/4.0/"@en .
"Graduate"@en .
"BIRS Workshop Lecture Videos (Banff, Alta)"@en .
"Mathematics"@en .
"Operations research, mathematical programming"@en .
"Computer science"@en .
"Applied computer science"@en .
"On the Optimality of Affine Policies for Budgeted Uncertainty Sets"@en .
"Moving Image"@en .
"http://hdl.handle.net/2429/70979"@en .