[Lowerbounds, Upperbounds]

Speaker: Adam Wierman

Time: Wednesday 12-1pm

Place: NSH 1507

Title: Understanding the effects of SMART scheduling

Abstract:

Recently, there have been a number of “scheduling success stories” where computer applications have provided improved performance by simply adjusting the way requests are queued. In applications such as web servers and routers, the heuristic of biasing towards small jobs has led to many of these successes. However, the policies that are implemented by practitioners do not match the idealized policies studied in theory. In my thesis, my goal is to illustrate that it is possible to bridge this gap by analyzing classes of scheduling policies instead of individual policies. In this talk, I will present one example of such a class: the SMART class, which includes a wide range of policies that prioritize jobs with small sizes. We will show that the SMART class is 2-competitive with respect to mean response time. Further, we will both derive stochastic bounds on the behavior of SMART policies and derive the asymptotic tail behavior of the SMART class.

Graph Partitioning using Single Commodity Flows

Rohit Khandekar
University of Waterloo

Feb 3, 15:30-16:30
Wean 7220

Graph partitioning is one of the fundamental optimization problems that has been extensively studied both in theory and practice. In this talk, we shall consider the problem of approximating the sparsest cuts in graphs. Almost all the previous algorithms for this problem use either eigenvector computations, multi-commodity flows, or solving semi-definite programs as sub-routines. While eigenvector based approaches yield poor approximation guarantees, the multi-commodity flows or SDP based algorithms are slow.

We show that the sparsest cuts can be approximated well using single commodity max-flow computations which are fast both in theory and perhaps more so in practice. Our algorithm iteratively computes max-flows to embed a complete graph and yields a certificate of expansion. Our technique can also be extended to obtain fast approximations for the balanced separator problem.

This is a joint work with Satish Rao and Umesh Vazirani (UC Berkeley).

TITLE: Hamilton cycles in random graphs (Dissertation Proposal)
SPEAKER: Kelley Burgin
WHEN: January 30, 1:30pm
WHERE: Porter Hall A19

ABSTRACT: We discuss the existence of Hamilton cycles in three different models of random graphs. In doing so, we present general proof techniques which include the differential equation method.

The first model is the random lift model introduced by Linial and Amit. For a fixed base graph K=(V,E), a random lift has vertex set V x [n] and for each edge (i,j) in E, there is a random perfect matching between {i} x [n] and {j} x [n]. We show that random lifts of the complete graph and complete bipartite graph contain a Hamilton cycle whp.

The second model is a random graph on n vertices in which (1-b)n vertices have degree 4 and the other bn vertices have degree 5. We show that for certain values of b, the graph is Hamiltonian whp.

The last model is a sparse random graph on n vertices with cn/2 random edges and minimum degree 3. We show that this random graph is Hamiltonian for c at least 3.01.

Why NP got a new definition: the quest to understand the approximation properties of NP-hard optimization problems

Sanjeev Arora
Princeton University

Friday, January 27, 2006
10:30am - SENSQ 5317

Abstract

Thousands of optimization problems in a variety of application areas are known to be NP-hard. Since no efficient exact algorithm is known, researchers have tried to understand the complexity of computing approximately optimal solutions. Surprisingly, NP-complete problems differ a lot in this respect. This talk is a survey of the many exciting results proved in the last 15 years in the quest to understand this phenomenon.

The first type of result shows nonapproximability: for many problems, computing approximate solutions is no easier than computing optimal solutions. This is shown by proving a new probabilistic characterization of NP, according to which it is possible to check certificates for membership in an NP language by examining a constant number of bits in the certificate. We will survey this result (the so-called PCP Theorem) and its many extensions.

The other type of result consists of designing better approximation algorithms. This endeavor has also been successful for many problems, and a large body of techniques has been developed in the past decade. We will survey some of these.

The talk will be self-contained.

I think we should make an active effort to avoid scheduling speakers from abroad to give talks in the last session, or perhaps even the one before that. I don’t know if this is entirely possible, but I feel bad when a fellow researcher, having flown all the way from half a globe away, has to give the last talk with a mostly empty room.

I know someone has to be in the last session. So yes, I will volunteer if we are to prevent this from happening again. My guess is that many of us in the community share this view too.

Imagine what can happen at the US border when you invite a speaker from a foreign country…

[T]he customs agents concluded that because Microsoft was covering my flight and accommodation, I was being compensated for consulting activities. In order to enter the country, I’d need a work permit.

http://www.darrenbarefoot.com/archives/2006/01/im-an-alien-an-illegal -alien.html

P.S. I don’t expect any speakers from the academic will have this problem, or so I hope.

Friday, January 20, 2006
1:30 p.m. Posner Hall 261

Javier Pena Professor, Tepper School of Business Carnegie Mellon University

Semidefinite Programming Relaxations for Polynomial Optimization Problems

A common paradigm in optimization is the use of well-understood models to address more complex problems. For instance, linear programming is used as a fundamental subroutine in branch-and-bound and branch-and-cut algorithms for integer programming. An interesting parallel is the use of semidefinite programming to address optimization problems involving polynomials. In this context semidefinite programming relaxations can often be obtained by a clever application of tools from algebraic geometry. In this presentation we will discuss some of the main ideas underlying these connections between semidefinite programming and algebraic geometry. We will also discuss some of the structural patterns that typically arise in the resulting semidefinite programming relaxations, and techniques to take advantage of such structure.

This is based on joint work with Juan Vera at Carnegie Mellon and Luis Zuluaga at University of New Brunswick in Canada.

I have to decide how this should be spelt. I guess since there is no dispute on how to spell “anonymous”, it should be “anonymnity”.

Google agrees, as of this morning:

787 for anonymnity vs. 564 for anonynmity

That’s quite a tongue-twister. I just tried to say an-non-NIM-nity ten times and I failed thrice.

UPDATE: Alex Tang points out in a comment that it should actually be “anonymity” (about 17,100,000 hits). Thanks!

AI Seminar 3:30pm, Tuesday Jan. 24, in Wean 5409

Title: Game theory, biology, and the binding game

Tommi Jaakkola
MIT CSAIL
http://people.csail.mit.edu/tommi/

Abstract:

Biological processes span across vastly different scales and necessarily have to be understood at multiple levels of abstraction. Towards clarifying the role that computation plays in such understanding, we have recently developed a class of game theoretic models for capturing coordinate operation of DNA binding regulators. Our work builds in part on the argument that the roles of various molecular interactions cannot be understood in isolation but that it is necessary to also capture the context provided by other mutually constraining processes. Our game theoretic model allocates proteins to neighborhoods of sites, and to sites themselves, in a resource constrained manner, while explicitly capturing coordinate and competitive relations among proteins with affinity to the site or region. We provide examples of known biological subsystems that are naturally translated into our framework, and illustrate predictions that can be derived from the model. The focus of the talk will be on mathematical foundations of the modeling approach and requires little or no biological background.

This is joint work with Luis Perez-Breva, Luis Ortiz, and Chen-Hsiang Yeang.

Speaker: Benoit Hudson

Time: Wednesday 12-1pm

Place: NSH 1507

Title: Time-Optimal Incremental Delaunay Refinement

Abstract:

Delaunay mesh refinement is widely used in scientific computing, because in practice it is fast. However, for about 10 years there were no time bounds on the technique faster than O(n^2). Indeed, many known algorithms exhibited quadratic-time behaviour in some bad cases that would occasionally be encountered in the wild. I will present the basic technique from Jim Ruppert’s 1995 paper, followed by the main ideas from Gary Miller SODA’04 paper that proves near-optimal time bounds. Time permitting, I will also touch on some more recent work Todd Phillips, Gary and I have done to extend the result to three (or more) dimensions.

Suppose we want to input the following sentence in LaTeX:

Therefore, the approximation ratio is 42.

Here is the obvious way:

Therefore, the approximation ratio is 42.

It works well, hmm, until that one day when you decide to change your math font. The correct way should be:

Therefore, the approximation ratio is $42$.

The dollar signs have a semantic meaning: “42″ is in the mathematical context, just as how we would input $x^2$. So if you intend to change the math font, then you want this occurrence to use that new font as well.

In case you want to see it in effect, here is a small example that you can try:

\documentclass{article}
\usepackage{ccfonts}
\usepackage[euler-digits]{eulervm}
 \begin{document}
\begin{enumerate}
\item 1 $1$ -1 $-1$ one
\item 2 $2$ -2 $-2$ two
\end{enumerate}
\end{document}

This example also shows the importance of the dollar signs when dealing with negative numbers. Without the dollar signs, the minus sign is actually a hyphen. This difference is very noticeable in the output. You can refer to this post if you want a reminder on hyphens (-), number ranges(–) and dashes(—).

Roy Levin, a friendly CMU alum, told us a story a couple weeks ago:

A job applicant was asked to write a 10-page description of a project he previously participated. The documentation of that project was well over a thousand pages and so he said there was no way to describe it in 10 pages… (The rest is history. )

Then Roy offered the following wisdom:

In a field that prides itself with the very idea of abstractions, everything can be explained in 10 pages. In fact, everything can be explained in one page. Good authors abstract the material to an appropriate level.

I suppose everyone agrees with his advice, but I wasn’t fully aware of that property of my field until he said it. I could have been doing it subconsciously before, but I do it consciously from that day on.

Yet it takes time and skill to do the abstraction right. I’ve seen positive and negative examples. In this regard, I remember a quote from Mark Twain, or Blaise Pascal, or really, Google:

I have written you a long letter because I did not have time to write a short one.

Some days I need to keep screaming in my head: I can explain this lucidly in 10 pages!

What do you expect if you run LaTeX on the following?

\documentclass{article}
\begin{document}
This is a $(\frac13, \frac23)$-separator.
\end{document}


Hint: it works.

P.S. In my experience, this “trick” is most useful for constant fractions with a one-digit numerator and a one-digit denominator. When in doubt, just use the braces, or you can learn why and how this works once and for all.

Command Prompt Here seems to be a well-known feature among the Windows users. It lets you right-click on a folder and open a command prompt with the current working directory set to that folder.

But what about its “functional inverse”, i.e., start an explorer to explore the current directory? Well, you can execute explorer . in the Command Prompt, but that will not be exactly “correct” since the tree view of folders is missing. Apparently you have to add a completely obscure argument… I put this command in a batch file on my path:

start "" explorer /e, .

Note that there cannot be a space between the “e” and the comma. Don’t ask.