- You are here:
- GT Home
- Home
- News & Events

Series: ACO Student Seminar

In this article, we disprove the uniform shortest path routing conjecture for vertex-transitive graphs by constructing an infinite family of counterexamples.

Series: ACO Student Seminar

Two independent proofs of the polyhedrality of the split closure of Mixed Integer Linear Program have been previously presented. Unfortunately neither of these proofs is constructive. In this paper, we present a constructive version of this proof. We also show that split cuts dominate a family of inequalities introduced by Koppe and Weismantel.

Series: ACO Student Seminar

Nash bargaining was first modeled in John Nash's seminal 1950 paper. In his paper, he used a covex program to give the Nash bargaining solution, which satifies many nature properties. Recently, V.Vazirani defined a class of Nash bargaining problem as Uniform Nash Bargaining(UNB) and also defined a subclass called Submodular Nash Bargaining (SNB). In this talk, we will consider some game theoretic issues of UNB: (1) price of bargaining; (2) fully competitiveness; (3) min-max and max-min fairness and we show that each of these properties characterizes the subclass SNB.

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.

Series: ACO Student Seminar

It has been found about ten years ago that most of the real networks are not random ones in the Erdos-Renyi sense but have different topology (structure of the graph of interactions between the elements of a network). This finding generated a steady flux of papers analyzing structural aspects of networks. However, real networks are rather dynamical ones where the elements (cells, genes, agents, etc) are interacting dynamical systems. Recently a general approach to the studies of dynamical networks with arbitrary topology was developed. This approach is based on a symbolic dynamics and is in a sense similar to the one introduced by Sinai and the speaker for Lattice Dynamical Systems, where the graph of interactions is a lattice. The new approach allows to analyze a combined effect of all three features which characterize a dynamical network ( topology, dynamics of elements of the network and interactions between these elements) on its evolution. The networks are of the most general type, e.g. the local systems and interactions need not to be homogeneous, nor restrictions are imposed on a structure of the graph of interactions. Sufficient conditions on stability of dynamical networks are obtained. It is demonstrated that some subnetworks can evolve regularly while the others evolve chaotically. Some natural graph theoretical and dynamical questions appear in the farther developments of this approach. No preliminary knowledge of anything besides basic calculus and linear algebra is required to understand what is going on.

Series: ACO Student Seminar

This study focuses on computations on large graphs (e.g., the web-graph) where the edges of the graph are presented as a stream. The objective in the streaming model is to maintain small amount of memory and perform few passes over the data.
In the streaming model, we show how to perform several graph computations including estimating the probability distribution after a random walk of certain length l, estimate the mixing time, and the conductance. We can compute the approximate PageRank values in O(nM^{-1/4}) space and O(M^{3/4}) passes (where n is the number of nodes and M is the mixing time of the graph). In comparison, a standard (matrix-vector multiplication) implementation of the PageRank algorithm will take O(n) space and O(M) passes. The main ingredient in all our algorithms is to explicitly perform several random walks of certain length efficiently in the streaming model. I shall define and motivate the streaming model and the notion of PageRank, and describe our results and techniques.
Joint work with Sreenivas Gollapudi and Rina Panigrahy from Microsoft Research.

Series: ACO Student Seminar

Constraint Programming is a powerful technique developed by the Computer Science community to solve combinatorial problems. I will present the model, explain constraint propagation and arc consistency, and give some basic search heuristics. I will also go through some illustrative examples to show the solution process works.

Series: ACO Student Seminar

The notion of a correlation decay, originating in statistical physics, has recently played an important role in yielding deterministic approximation algorithms for various counting problems. I will try to illustrate this technique with two examples: counting matchings in bounded degree graphs, and counting independent sets in certain subclasses of claw-free graphs.

Series: ACO Student Seminar

A successful approach to solving linear programming problems exactly has been to solve the problems with increasing levels of fixed precision, checking the final basis in exact arithmetic and then doing additional simplex pivots if necessary. This work is a computational study comparing different techniques for the core element of our exact computation: solving sparse rational systems of linear equations exactly.

Series: ACO Student Seminar

In order to estimate the spread of potential pandemic diseases and the efficiency of various containment policies, it is helpful to have an accurate model of the structure of human contact networks. The literature contains several explicit and implicit models, but none behave like actual network data with respect to the spread of disease. We discuss the difficulty of modeling real human networks, motivate the study of some open practical questions about network structure, and suggest some possible avenues of attack based on some related research.