Series: ACO Distinguished Lecture
RECEPTION TO FOLLOW
Fifty five years ago, two results of the Hungarian mathematicians, Koenig and Egervary, were combined using the duality theory of linear programming to construct the Hungarian Method for the Assignment Problem. In a recent reexamination of the geometric interpretation of the algorithm (proposed by Schmid in 1978) as a steepest descent method, several variations on the algorithm have been uncovered, which seem to deserve further study. The lecture will be self-contained, assuming little beyond the duality theory of linear programming. The Hungarian Method will be explained at an elementary level and will be illustrated by several examples. We shall conclude with account of a posthumous paper of Jacobi containing an algorithm developed by him prior to 1851 that is essentially identical to the Hungarian Method, thus anticipating the results of Koenig (1931), Egervary (1931), and Kuhn (1955) by many decades.
Conditionals on structural properties of strings and their stochastic counterparts in a declarative formalism
Series: Stochastics Seminar
Many context-free formalisms based on transitive properties of trees and strings have been converted to probabilitic models. We have Probabilistic Finite Automaton, Probabilistic Context Free Grammar and Probabilistic Tree Adjoining Grammars and many other probabilistic models of grammars. Typically such formalisms employ context-free productions that are transitively closed. Context-free grammars can be represented declaratively through context-sensitive grammars that analyse or check wellformedness of trees. When this direction is elaborated further, we obtain constraint-based representations for regular, context-free and mildly-context sensitive languages and their associated structures. Such representations can also be Probabilistic and this could be achieved by combining weighted rational operations and Dyck languages. More intuitively, the rational operations are packed to a new form of conditional rule: Generalized Restriction or GR in short (Yli-Jyrä and Koskenniemi 2004), or a predicate logic over strings. The conditional rule, GR, is flexible and provides total contexts, which is very useful e.g. when compiling rewriting rules for e.g. phonological alternations or speech or text normalization. However, the total contexts of different conditional rewriting rules can overlap. This implies that the conditions of different rules are not independent and the probabilities do not combine like in the case of context-free derivations. The non-transitivity causes problems for the general use of probabilistic Generalized Restriction e.g. when adding probabilities to phonological rewriting grammars that define regular relations.
Wednesday, November 12, 2008 - 14:00 , Location: Skiles 255 , Christian Houdré , School of Mathematics, Georgia Tech , Organizer: Christian Houdre
In connection with the class Stochastic Processes in Finance II, we will have a supplementary lecture where a first, 50 minutes long, movie on Doeblin's life will be shown. This will be followed by a second movie, 30 minutes long, where Yor explains on the blackboard Doeblin's contribution to what Shreeve calls the Ito-Doeblin's lemma.
On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP
Series: ACO Student Seminar
We consider the following Maximum Budgeted Allocation(MBA) problem: Given a set of m indivisible items and n agents; each agent i is willing to pay b_ij amount of money on item j, and in addition he species the maximum amount (budget of B_i) he is willing to pay in total over all the items he receives. Goal is to allocate items to agents so as to maximize the total payment received from all the agents. The problem naturally arises as auctioneer revenue maximization in first price budget-constrained Auctions (For e.g. auctioning of TV/Radio ads by Google). Our main results are: 1) We give a 3/4-approximation algorithm for MBA improving upon the previous best of 0.632 [Anelman-Mansour, 04]. Our factor matches the integrality gap of the LP used by the previous results. 2) We prove it is NP-hard to approximate MBA to any factor better than 15/16, previously only NP-hardness was known. Our result also implies NP-hardness of approximating maximum submodular welfare with demand oracle to a factor better than 15/16, improving upon the best known hardness of 275/276 [Feige-Vondrak, 07]. Our hardness techniques can be modified to prove that it is NP-hard to approximate the Generalized Assignment Problem (GAP) to any factor better than 10/11. This improves upon the 422/423 hardness of [Chekuri-Kumar, 04]. We use iterative rounding on a natural LP relaxation of MBA to obtain the 3/4-approximation. Recently iterative rounding has achieved considerable success in designing approximation algorithms. However, these successes have been limited to minimization problems, and as per our knowledge, this work is the first iterative rounding based approximation algorithm for a natural maximization problem. We also give a (3/4 - \epsilon)-factor algorithm based on the primal-dual schema which runs in O(nm) time, for any constant \epsilon > 0. In this talk, I will present the iterative rounding based algorithm, show the hardness reductions, and put forward some directions which can help in solving the natural open question of closing the approximation gap. Joint work with Deeparnab Chakrabarty.
Wednesday, November 12, 2008 - 11:00 , Location: Skiles 255 , Benjamin Ridenhour , CDC/CCID/NCIRD, CTR , Organizer:
Parent-offspring interactions lead to natural conflicts. Offspring want as many resources as possible from parents in order to gain maximal fitness levels. On the other hand, parents desire to invest only enough to guarantee survival to reproduction. The resolution of the parent-offspring conflict has been a topic of much debate in evolutionary biology and typically invoke the concept of 'costs' to begging by offspring. Here I present the analysis of a simple quantitative genetic model of parent-offspring interactions that does not costs to resolve parent-offspring conflicts.
Series: PDE Seminar
We discuss the inverse problem of determining elastic parameters in the interior of an anisotropic elastic media from dynamic measurements made at the surface. This problem has applications in medical imaging and seismology. The boundary data is modeled by the Dirichlet-to-Neumann map, which gives the correspondence between surface displacements and surface tractions. We first show that, without a priori information on the anisotropy type, uniqueness can hold only up to change of coordinates fixing the boundary. In particular, we study orbits of elasticity tensors under diffeomorphisms. Then, we obtain partial uniqueness for special classes of transversely isotropic media. This is joint work with L. Rachele (RPI).
Series: Dissertation Defense
Series: Analysis Seminar
It is easy to ask for the number T(g,n) of (rooted) graphs with n edges on a surface of genus g. Bender et al gave an asymptotic expansion for fixed g and large n. The contant t_g remained missing for over 20 years, although it satisfied a complicated nonlinear recursion relation. The relation was vastly simplified last year. But a further simplification was made possible last week, thus arriving to Painleve I. I will review many trivialities and lies about this famous non-linear differential equation, from a post modern point of view.
Monday, November 10, 2008 - 13:00 , Location: Skiles 255 , Guowei Wei , Michigan State University , Organizer: Haomin Zhou
Solvation process is of fundamental importance to other complex biological processes, such signal transduction, gene regulation, etc. Solvation models can be roughly divided into two classes: explicit solvent models that treat the solvent in molecular or atomic detail while implicit solvent models take a multiscale approach that generally replaces the explicit solvent with a dielectric continuum. Because of their fewer degrees of freedom, implicit solvent methods have become popular for many applications in molecular simulation with applications in the calculations of biomolecular titration states, folding energies, binding affinities, mutational effects, surface properties, and many other problems in chemical and biomedical research. In this talk, we introduce a geometric flow based multiscale solvation model that marries a microscopic discrete description of biomolecules with a macroscopic continuum treatment of the solvent. The free energy functional is minimized by coupled geometric and potential flows. The geometric flow is driven not only by intrinsic forces, such as mean curvatures, but also by extrinsic potential forces, such as those from electrostatic potentials. The potential flow is driven mainly by a Poisson-Boltzmann like operator. Efficient computational methods, namely the matched interface and boundary (MIB) method, is developed for to solve the Poisson- Boltzmann equation with discontinuous interface. A Dirichlet- to-Neumann mapping (DTN) approach is developed to regularize singular charges from biomolecules.
Series: Combinatorics Seminar
Given a set of linear equations Mx=b, we say that a set of integers S is (M,b)-free if it contains no solution to this system of equations. Motivated by questions related to testing linear-invariant Boolean functions, as well as recent investigations in additive number theory, the following conjecture was raised (implicitly) by Green and by Bhattacharyya, Chen, Sudan and Xie: we say that a set of integers S \subseteq [n], is \epsilon-far from being (M,b)-free if one needs to remove at least \epsilon n elements from S in order to make it (M,b)-free. The conjecture was that for any system of homogeneous linear equations Mx=0 and for any \epsilon > 0 there is a *constant* time algorithm that can distinguish with high probability between sets of integers that are (M,0)-free from sets that are \epsilon-far from being (M,0)-free. Or in other words, that for any M there is an efficient testing algorithm for the property of being (M,0)-free. In this paper we confirm the above conjecture by showing that such a testing algorithm exists even for non-homogeneous linear equations. As opposed to most results on testing Boolean functions, which rely on algebraic and analytic arguments, our proof relies on results from extremal hypergraph theory, such as the recent removal lemmas of Gowers, R\"odl et al. and Austin and Tao.