Name: Osman Oguz
University: Bilkent University
Date: Friday, November 9, 2007
Time: 1:30 to 3:00 pm
Location: 388 Posner Hall
Title: Cardinality Cuts: New Universal Cutting Planes for Integer Programming
Abstract:
We present new valid inequalities for 0-1 programming problems that work in similar ways to well known cover inequalities. The differences exist in three aspects. The first is in the generation of the inequalities. The method used in generation of the new cuts involves solving linear programs only. Second difference is the more general applicability, i.e., being useful for problems like TSP and general integer programming problems. The third aspect is superior effectiveness as indicated by the computational experiments.
November 7, 2007
12:00 PM, 1507 Newell-Simon Hall
Virginia Vassilevska
Title: Nondecreasing Paths in a Weighted Graph or: How to Optimally Read a Train Schedule
Abstract:
A travel booking office has timetables giving arrival and departure times for all scheduled trains, including their origins and destinations. A customer presents a starting city and demands a route with perhaps several train connections taking him to his destination as early as possible. The booking office must find the best route for its customers. This problem was first considered in the theory of algorithms in 1958 by George Minty, who reduced it to a problem on directed edge-weighted graphs: find a path from a given source to a given target such that the consecutive weights on the path are nondecreasing and the last weight on the path is minimized. Minty gave the first algorithm for the single source version of the problem, in which one finds minimum last weight nondecreasing paths from the source to every other vertex. In this talk we present the first linear time algorithm for this problem. The algorithm uses some nice data structures and is surprisingly simple and elegant.
November 9, 2007
10:30 AM, 5409 Wean Hall
Daniel Golovin
Thesis Proposal
Title: Uniquely Represented Data Structures with Applications to Privacy
Abstract:
In a typical application storing some data, if the memory representations of the internal data structures are inspected, they may leave significant clues to the past use of the application. For example, a data structure with lazy deletions might retain an object that the user believes was deleted long ago; this is problematic in environments requiring high security or strict privacy guarantees. We can eliminate such problems entirely by demanding that a data structure implementation store exactly the information specified by an abstract data type (ADT), and nothing more. To do this, it is often necessary and always sufficient to ensure the data structure is uniquely represented. That is, any two sequences of operations which bring the ADT to the same logical state will cause the implementation to generate the same memory representation. If we allow randomization, we allow the memory representation of each logical state to vary with the random bits, but require the data structure to be uniquely represented for each fixed sequence of random bits. This observation begs the following question.
For each abstract data type, what is the added cost for uniquely represented implementations over their conventional counterparts, in terms of time, space, and randomness?
In the proposed thesis, we will answer this question for several important abstract data types, and demonstrate that the overhead for unique representations is sufficiently low to warrant their widespread use in high security and high privacy environments.
Thesis Committee:
Guy Blelloch, Chair
Gary L. Miller
R. Ravi
Jon M. Kleinberg, Cornell University
Title: Local anti-Ramsey numbers
Speaker: Tao Jiang (Miami University, Oxford, OH)
When: November 8, 16:30-17:30
Where: Wean Hall 5302
Abstract:
Anti-Ramsey problems usually refer to the study of rainbow subgraphs in an edge-colored host graph, where a subgraph is rainbow if all of its edges have different colors. The anti-Ramsey number of a graph H for a given integer n, denoted by AR(n,H), is the maximum number of colors of an edge-coloring of the complete graph K_n that contrains no rainbow copy of H. The idea is that as one increases the overall number of colors used on K_n, eventually one must force a rainbow copy of H. This can be viewed as Turan analogue for edge-colorings. The anti-Ramsey numbers were introduced by Erdos, Simonovits, and Sos in the 1970’s. Many news results were obtained in recent years.
Axenovich, Jiang, Tuza introduced the notion of local anti-Ramsey numbers. The goal is to study the threshold on the number of colors appearing at each vertex beyond which a rainbow copy of H is forced. They also considered properly colored copy of H. Several problems they raised remain unsolved. The main difficulty seems to be that when one imposes a condition on the color degree (the number of different colors appearing at a vertex) it has little global effect, and often one gets closer to extremal values by using highly unbalanced colorings. So, most techniques based on counting seem to fail. In this seminar talk, we review these problems and the partial results. We answer one of the conjectures raised by them affirmatively. That is, for every k, there exists an absolutely constant lambda_k such that in every edge-coloring of K_n in which the color degree of each vertex is at least lambda_k, there exists a properly cycle of length exactly k.
