Seminars for Fall 2012

10/11/12 RUTCOR Colloquium - 1:30 PM

Speaker: Gyula O.H. Katona
Affiliation: Alfred Renyi Instutute of Mathematics, Budapest
Title: Cryptology, isoperimetric problems and shadows

See abstract

10/04/12 RUTCOR Colloquium - 1:30 PM

Speaker: Andrey Garnaev
Affiliation: St Petersburg State University
Title: Search games with resource allocation

Abstract: In this presentation we suggest two new classes of search games. The first class is screening and hiding versus searching games. This class of search games is motivated by the book Search and Screening by Koopman who is the founder of the modern search theory. In our game a hider not just trying to find the best place to hide from a searcher, but also he applies efforts to screen his allocation making more difficult for a searcher to catch him. This hiding and screening strategy of the hider versus search strategy of the searcher makes the scenario more real-world relative comparing to widely investigated in literature just hiding versus searching games. The second class of the search game is search game in which a hider has partial information about a searcher's resource. Say, the hider can be a terrorist trying to hide and the searcher can be special forces trying to catch him, terrorist does not know the number of forces involved in the search but just its distribution. These scenario are modeled by non-zero-sum games with resources allocation. Note that the considered problems also can be motivated by network's security. Say, the second problem in network s security term s can be reformulated as follows. There are a defender (say, network's provider) and an attacker (say, a hacker). The defender seeks to minimize network risk (say, lost data - bits of information stored in network's nodes) by relocating stored data and allocating resources to reduce the vulnerability of individual components in the network, and the other player, the attacker, seeks to maximize possible network's data lost by allocating defensive resources. The problem shows how this joint control over defensive budget and stored data reduces network's risks and how it increases flexibility and efficiency of defensive strategy. We also give a brief survey of related problems.

09/13/12 RUTCOR Colloquium - 1:30 PM

Speaker: Dr. Khaled Elbassioni
Affiliation: Max Planck Institute, Saarbrucken, Germany
Title: Approximation Algorithms for Non-Single-minded Profit-Maximization Problems with Limited Supply

Abstract: We consider profit-maximization problems for combinatorial auctions with non-single minded valuation functions and limited supply. We present fairly general results that relate the approximability of the profit-maximization problem to that of the corresponding social-welfare-maximization (SWM) problem, which is the problem of finding an allocation $(S_1,\ldots,S_n)$ satisfying the capacity constraints that has maximum total value $\sum_j v_j(S_j)$. This yields approximation algorithms for both structured valuation classes, such as subadditive valuations and tree-paths valuations, as well as arbitrary valuations. For a special case, known as the non-single minded highway problem, we will present a different approximation algorithm based on configuration LP's.
This is joint work with Mahmoud Fouz and Chaitanya Swamy.

We have two Seminar Series: Brown Bag Talks and RUTCOR Colloquia.

Brown Bag Talks are usually on Thursdays, 12:00-1:00, in the RUTCOR lounge. Pizza is served but feel free to bring your own lunch. The Brown Bag Series usually host speakers from the RUTCOR community.

RUTCOR Colloquia are usually held Thursdays, 1:30-2:30 PM, in the Seminar Room or Room 139. The RUTCOR Colloquia feature speakers from outside the RUTCOR community.

Special Joint MSIS/RUTCOR Seminar Series are held at
One Washington Park #1027
Video conference Levin #130

Research Areas

Discrete and Combinatorial Optimization
Linear and Nonlinear Programming
Stochastic Optimization
Boolean methods in Operations Research
Queuing Theory
Logical Analysis of Data

Contact Information

If you would like to be one of our speakers, please contact:
Terry Hart