Industrial Engineering Seminar

The Industrial Engineering seminar provides a platform for guests and members of the Industrial Engineering groups to report on their research. The presentations are also understandable for non-specialists. The seminar takes place on a weekly basis

Tuesday, 12:45—13:30, Citadel H327

Next presentation:

Bodo Manthey, Stochastic Mean Payoff Games: Smoothed Analysis and Approximation Schemes

Date & Location:	February 21, 12:45-13:30, Ci H327
Speaker:	Bodo Manthey
Affiliation:	UT-EWI-DMMP
Abstract:	Stochastic mean payoff games are a powerful class of two-player zero-sum games that generalize, e.g., cyclic games, simple stochastic games, parity games, and Markov decision processes. A stochastic mean payoff game consists of a directed graph with black, white, and red vertices: Black and white vertices belong to the two players, red vertices are random vertices. The edges are labeled with rewards. During the game a token is moved along the edges, and the black player pays the white player the corresponding reward. The goal of the players is to optimize their average payment. The question whether equilibrium strategies and game values of stochastic mean payoff games can be computed efficiently is a long-standing open problem. It is only known that this problem lies in the intersection of NP and co-NP, and there are pseudo-polynomial algorithms for some subclasses. To get some more insights into the complexity of solving these games, we consider two relaxed concepts: Approximate Nash equilibria and smoothed analysis. In the former, players are happy with a strategy if they cannot gain too much by deviating. In the latter, we rule out pathological instances by perturbing the rewards. We prove that the existence of pseudo-polynomial algorithms implies the existence of approximation schemes and polynomial smoothed complexity. (Joint work with Endre Boros, Khaled Elbassioni, Mahmoud Fouz, Vladimir Gurvich, and Kazuhisa Makino.)

Upcoming presentations:

Feb 21	Bodo Manthey (UT-EWI-DMMP)	Stochastic Mean Payoff Games: Smoothed Analysis and Approximation Schemes

Past presentations:

2012

Feb 14	Veselin Jungic (Simon Fraser University)	On monotone and double arithmetic progressions
Jan 24	Malte Risto (UT-CTW-CTS)	The social dilemma of traffic flow improvement: using the example of Connected Cruise Control

2011

Dec 6	Ruben van der Zwaan (Maastricht University)	Preemptive and Non-Preemptive Generalized Min Sum Set Cover
Nov 22	Maartje Zonderland (UT-EWI-SOR)	Planning and Scheduling of Semi-Urgent Surgeries: Implementation Study in Neurosurgery
Nov 15	Ove Göttsche (UT-EWI-SST)	The deconvolution operator and the difference of convex risk measures
Nov 7	Sandeep Juneja (Tata Institute of Fundamental Research, Mumbai, India)	The Concert/Cafeteria Queueing Game with a Fluid/Finite Population
Nov 1	Berend Roorda (UT-MB-F&A)	The impact of risk on value: axioms, unique updating, and the role of dynamic programming
Oct 25	Sameh Haneyah (UT-MB-OMPL)	Generic Planning and Control of Automated Material Handling Systems (AMHSs)
Oct 18	Harm Bossers (UT-EWI-DMMP)	Online Outlier Detection in Testing of Integrated Circuits using KernelDensity Estimation
Sep 20	Ruben Hoeksma (UT-EWI-DMMP)	Decentralized Scheduling Solutions: a Game Theoretic Approach
July 12	Mariana Olvera-Cravioto (Columbia University)	Weighted Branching Processes with Mixed Signed Weights
June 14	Konstantin Avratchenkov (INRIA)	Socially-Aware and Cooperative Network Formation Games
May 31	Maarten IJzerman (UT-MB-HTSR)	Decision making in medicine and medical product development
May 17	Andreas Fügener (Technische Universität München)	Master Surgery Scheduling under Consideration of Multiple Downstream Units
May 3	Jasper Goseling (UT-EWI-SOR)	The Potential of Network Coding in Wireless Communications
May 2	Yana Volkovich (Barcelona Media Innovation Centre)	Social apples and oranges: a study of the different social networks
April 26	Maartje van de Vrugt	Model Based Control - Improving efficiency on wastewater treatment plants
April 12	Bodo Manthey (UT-EWI-DMMP)	Smoothed Analysis of Euclidean Functionals
April 5	Anthony Ohazulike (UT-CTW-CTS)	Multi-Objective Road Pricing: A Competitive and Cooperative Multi-level Approach
Feb 15	Elisa Alvarez (UT-MB-OMPL)	The selective use of emergency shipments for service-contract differentiation
Feb 8	Jaroslav Krystul (UT-EWI-SST)	Splitting Methods for Rare–Event Simulation: Some Issues in Large–Scale Stochastic Hybrid Systems

2010

Dec 14	Reinoud Joosten (UT-MB-F&A)	Stochastic games with endogenous transitions
Nov 30	B.V. Raghavendra Rao (Saarland University)	Probabilistic Analysis of Christofides' Algorithm
Nov 16	Jan Telgen (UT-MB-OMPL)	OR challenges in Purchasing management
Nov 9	Anna Khmelnitskaya	Tree-type values for cycle-free directed graph games
Oct 5	Carl Chiarella (University of Technology, Sydney, and Convenor, Financial Integrity Research Network, Australia)	The Evaluation of Barrier Option Prices under Stochastic Volatility
Sep 28	Alje van den Bosch	Proportional Fair Ramp Metering
Aug 24	Daniel Paulusma (Durham University)	Narrowing Down the Gap on the Complexity of Coloring P_k-Free Graphs
July 6	Yoni Nazarathy (TU/e, EURANDOM)	Model predictive control for queueing networks
June 29	Michel Vellekoop (UvA)	Sahara Utility and Optimal Investment and Consumption
June 22	Ali Eshragh (University of South Australia)	Hamiltonian Cycles, Random Walks and Discounted Occupational Measures
June 8	Kolja Loebniz (UT-MB-F&A)	Quantitative Liquidity Risk Management in Banks
May 18	Tom van Woensel (TU/e)	Self-Imposed Time Windows in Vehicle Routing Problems with Stochastic Service Times and Fixed Shift Duration
May 11	Henk Zijm (UT-MB-OMPL)	Stochastic Models for Manufacturing Systems
April 29	Mahmoud Fouz (Saarland University, Saarbrücken, Germany)	Asymptotically Optimal Randomized Rumor Spreading
April 28	Khaled Elbassioni (Max-Planck-Institut Informatik, Saarbrücken, Germany)	Every Stochastic Game with Perfect Information Admits a Canonical Form
April 27	Arun Bagchi (UT-EWI-SST)	Application of Particle Filtering in Mathematical Finance
April 6	Georg Still (UT-EWI-DMMP)	Wardrop vs Nesterov traffic equilibrium model
March 31	Aymeric Lardon (Université de St. Etienne, France)	The γ-core in Cournot oligopoly TU-games with capacity constraints
March 30	Marc Wouters (UT-MB-F&A)	Management of early-stage new product development projects: a simplified options approach
March 23	Judith Vink-Timmer (UT-EWI-SOR)	Cost Sharing in a Tandem Network
March 16	Wim Albers (UT-EWI-SP)	Negative Binomial control charts for health care monitoring
March 9	Marc Uetz (UT-EWI-DMMP)	Mechanism Design & Scheduling
Mar 2	Bodo Manthey (UT-EWI-DMMP)	Approximation Algorithms for Multi-Criteria Traveling Salesman Problems
Feb 2	Anna Khmelnitskaya (SPb Institute for Economics and Mathematics Russian Academy of Sciences)	On 1-convexity and nucleolus of co-insurance games
Jan 19	Holger I. Meinhardt (Institute for Statistics and Economic Theory, University of Karlsruhe)	A Dual Pre-Kernel Representation based on the Fenchel-Moreau Conjugation of the Characteristic Function

2009

Dec 15	Jing Bie (UT-CTW-CTS)	As complex as it can be: day-to-day traffic dynamics
Dec 8	Johann Hurink (UT-EWI-DMMP)	Changes in the Energy Supply Chain
Dec 1	Eric van Berkum (UT-CTW-CTS)	Route Choice Modelling in Traffic Assignment
Nov 24	Erwin Hans (UT-MB-OMPL)	Optimization of healthcare processes - an introduction of the research collaboration within the SRO IE&ICT

The Industrial Engineering Seminar was previously known as the dinsdagseminarium which has been taking place since 2004. Details of past presentations in the dinsdagseminarium can be found here.