Select a calendar:
Filter March Events by Event Type:
SUNMONTUEWEDTHUFRISAT
Events for March 30, 2010
-
Solution Methods to Problems that Involve Discrete Choice Constraints
Tue, Mar 30, 2010 @ 03:30 PM - 04:30 PM
Daniel J. Epstein Department of Industrial and Systems Engineering
University Calendar
DANIEL J. EPSTEIN DEPARTMENT OF INDUSTRIAL & SYSTEMS ENGINEERING SEMINAR:Title: "Solution Methods to Problems that Involve Discrete Choice Constraints"Speaker: Dr. Stephen Stoyan, Visiting Assistant Professor, Daniel J Epstein Department of Industrial and Systems Engineering, University of Southern CaliforniaABSTRACT: There are a number of practical problems in health care, supply-chain management, energy, and finance that involve the decision or selection of a subset of elements within the system. In each case, the problem equates to solving a mixed-integer program with discrete choice constraints. Due to an inherent NP-hard subproblem, such models are difficult to solve and commercial solvers will not provide optimal solutions. We present an iterative penalty algorithm that takes advantage of problem structure and generates solutions for practical instances. The algorithms performance is illustrated in a financial example involving portfolio selection, where the results are compared to a commercial solver and other approaches. Even greater performance is achieved for large-scale instances when uncertainty is added to the problem. Such designs can be applied to patient scheduling and supply-chain network models, where the approach represents a markedly different but effective method with respect to the literature. We show that the algorithm performs remarkably well in comparison to a well-known benchmark and solutions are generated within reasonable time frames.TUESDAY, MARCH 30, 2010, ANDRUS GERONTOLOGY BUILDING, (GER) ROOM 309, 3:30 – 4:30 PM
Location: Ethel Percy Andrus Gerontology Center (GER) - 309
Audiences: Everyone Is Invited
Contact: Georgia Lum
-
CS Colloq: Alexandra Kolla
Tue, Mar 30, 2010 @ 03:30 PM - 05:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Talk Title: New Techniques for Using and Approximating Graph SpectraSpeaker: Dr. Alexandra Kolla Host: Prof. David KempeAbstract:
In this talk, we present novel techniques, based on spectral graph theory, and how they are used to design efficient algorithms for both practical and theoretical problems.
In the first part of the talk, we present new techniques for approximating a large graph with a smaller one. Namely, we show how, given a large graph G and a subgraph H of it, we can choose a very small number of edges H' out of H such that replacing H with H' does not change the spectrum of G by much.
We discuss significant implications of our techniques in two interesting practical problems: creating cost-efficient, well-connected networks and speeding up linear system solvers.
In the second part of the talk we present how spectral techniques can be useful for investigating the validity of Khot's Unique Games conjecture (UGC). UGC is one of the most central open problems in computational complexity theory. It asserts that for a certain constraint satisfaction problem, it is NP-hard to decide whether there is a labeling that satisfies almost all the constraints or, for every labeling, the fraction of the constraints satisfied is very small.
Since its origin, the UGC has been applied with remarkable success to prove tight hardness of approximation results for several important NP-hard problems such as Vertex Cover, MaxCut.
We discuss a novel spectral algorithm for deciding satisfiability of Unique Games. We show that our spectral approach works well on instances that previous techniques -which were solely based on linear and semidefinite
programming- provably fail.Bio:
I got my PhD at U.C Berkeley. My advisor was Umesh Vazirani. I am a postdoc at the Institute for Advanced Study in Princeton. My main area of interest is Theory of Computer Science and in particular spectral graph theory, convex programming and their implications to efficient algorithmic design. I am also interested in quantum computing and cryptography.
Bio: TBA
Location: Seaver Science Library (SSL) - 150
Audiences: Everyone Is Invited
Contact: CS Front Desk
