Optimization seminar

Modal title

Modal content

Date / Time

Speaker

Title

Location

1 April 2019
16:30-17:30

Dr. Emily Speakman
Otto von Guericke University, Magdeburg, Germany

Event Details

Title	Gaining or losing perspective
Speaker, Affiliation	Dr. Emily Speakman, Otto von Guericke University, Magdeburg, Germany
Date, Time	1 April 2019, 16:30-17:30
Location	HG G 19.1
Abstract	We study mixed-integer nonlinear-optimization formulations of the disjunction $x\in\{0\}\cup[l,u]$, where $z$ is a binary indicator of $x\in[l,u]$, and $y$ ``captures'' $x^p$, for $p>1$. This model is useful when activities have operating ranges, we pay a fixed cost for carrying out each activity, and costs on the levels of activities are strictly convex. One well-known concrete application (with $p=2$) is mean-variance optimization (in the style of Markowitz). Using volume as a measure to compare convex bodies, we investigate a family of relaxations for this model, employing the inequality $yz^q \geq x^p$, parameterized by the ``lifting exponent'' $q\in [0,p-1]$. These models are higher-dimensional-power-cone representable, and hence tractable. We analytically determine the behavior of these relaxations as functions of $l,u,p$ and $q$, enabling use in modeling and algorithmic decisions. We validate our results computationally, for the case of $p=2$. Furthermore, for $p=2$, we give results on optimal branching-point selection (in the context of spatial branch-and-bound). This is joint work with J. Lee (Michigan) and D. Skipper (USNA).

Gaining or losing perspectiveread_more

13 May 2019
16:30-17:30

Dr. Sagar Kale
EPF, Lausanne

Event Details

Title	Beating Greedy for Stochastic Bipartite Matching
Speaker, Affiliation	Dr. Sagar Kale, EPF, Lausanne
Date, Time	13 May 2019, 16:30-17:30
Location	HG G 19.1
Abstract	We consider the maximum bipartite matching problem in stochastic settings, namely the query-commit and price-of-information models. In the query-commit model, an edge e independently exists with probability p_e. We can query whether an edge exists or not, but if it does exist, then we have to take it into our solution. In the unweighted case, one can query edges in the order given by the classical online algorithm of Karp, Vazirani, and Vazirani to get a (1-1/e)-approximation. In contrast, the previously best known algorithm in the weighted case is the (1/2)-approximation achieved by the greedy algorithm that sorts the edges according to their weights and queries in that order. Improving upon the basic greedy, we give a (1-1/e)-approximation algorithm in the weighted query-commit model. We use a linear program (LP) to upper bound the optimum achieved by any strategy. The proposed LP admits several structural properties that play a crucial role in the design and analysis of our algorithm. We also extend these techniques to get a (1-1/e)-approximation algorithm for maximum bipartite matching in the price-of-information model introduced by Singla, who also used the basic greedy algorithm to give a (1/2)-approximation.

Beating Greedy for Stochastic Bipartite Matchingread_more

Note: if you want you can subscribe to the iCal/ics Calender.

Archive: SS 22 SS 20 AS 19 SS 19 AS 18 SS 18 AS 17 SS 17 AS 16 SS 16 AS 15 SS 15 AS 14 SS 14 AS 13 SS 13 AS 12 SS 12 AS 11 SS 11 AS 10 SS 10 AS 09