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
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.