## Tuesday, January 29, 2008

### Homework 2

Homework 2 is up on the course web page: I will also put a bunch of copies outside Nicole Stenger's office (Wean 4116) that you could pick up....

### Example for Primal-Dual fixed

The bad example for the primal-dual algorithm that I cooked up in class did not give the large gap I was hoping for, though going in the right direction. Instead, consider the following example:

There are $2n$ clients and $n$ potential facilities. The first $n$ of the clients (say $v_1, v_2, \ldots, v_n$) are at distance 1 to all the facilities, we call these communal clients.

For the other $n$ clients: client $v_{n+i}$ is at distance $1$ to facility $u_i$ and at distance 3 to all other facilities. (We say client $v_{n+i}$ is facility $u_i$'s private client.)

The first facility $u_1$ costs $n+1$, and all the others cost $n+2$.

If we raise duals uniformly, then at time $t=2$, the first facility $u_1$ will become tentatively opened, and all the communal clients, and private client $u_{n+1}$ become frozen. But the other private clients will continue to raise their duals, and at time $t=3$, all the remaining facilities will also become tentatively open.

Note that the cost of actually opening all these tentatively open facilities would be $(n+1) + (n-1)(n+2) = \Omega(n^2)$, whereas the total dual value generated is only $O(n)$.

Hence the clean-up step is needed.

### Facility Location -- no joke

Facility Location is one of the theory problems studied most extensively in practice. It has obvious appeal in industry and is the subject of numerous books and optimization heuristics.

I especially like how the special case of the "Fermat-Weber problem" in the plane was already studied for its use in practice (minimizing industrial transportation cost) in 1909.

## Monday, January 28, 2008

### Some more LP notes

Here is the chapter dealing with LP duality from the textbook Understanding and Using Linear Programming by Jiří Matoušek and Bernd Gärtner.

Two caveats: the file is somewhat large (4 megs), and is accessible only from cmu.edu web addresses.

## Saturday, January 26, 2008

### Notes on Linear Programming

You may want to brush up on your linear programming; LP duality will be important for tomorrow's lecture.

For a relatively quick (40 pages) summary of the topic I usually go to Goemans's lecture notes. However these do not include the Ellipsoid Algorithm, which is of great theoretical importance for showing linear programming (and extensions, e.g., semidefinite programming) is in P.

For more details, Avner Magen's lecture notes look pretty thorough.

### Nina and Avrim's problem

Nina just told me a nice approximation algorithms problem she has written about with Avrim -- "Graph Vertex Pricing".

Stripping out the econ motivation, the problem is as follows:

Input: an undirected graph with nonnegative weights $w(u,v)$ on the edges.

Output: a nonnegative "price" $p(v)$ on each vertex.

Value: For each edge $(u,v)$ such that $p(u) + p(v) \leq w(u,v)$, you gain $p(u) + p(v)$. Otherwise you gain $0$ for that edge.

Determining $Opt$ is NP-hard, and it's also known [Guruswami-Hartline-Karlin-Kempe-Kenyon-McSherry] to be "APX-hard"; i.e., there is no PTAS unless P = NP.

Nina and Avrim have a paper giving a factor-$4$ approximation algorithm (among many other things). You might want to see if you can think of this algorithm yourself (hint: reduce to the bipartite case; lose a factor of 2 twice).

This seems to me like a very nice problem to work on -- improving either the algorithm or the hardness. One tricky aspect of it is that no one can think of a LP relaxation...

## Thursday, January 24, 2008

### You too can post to the blog

If you didn't sign up in the first class but want to post to the blog, just send us an email.

(Excellent usage of this feature by Jeremiah in clarifying homework problem 3, for example.)

### Homework 1 problem 4b correction

This should say "... for all constant $c \lt 5/4$..." not $\gt$. Corrected in the .pdf on the course page. (Thanks Kanat.)

### Homework 1 Clarification

For problem 3 we use Max-E3SAT-6. When it says that each variable appears in exactly 6 clauses does this mean that (x, not x) each appear 6 in six clauses or are they not considered separate variables?

## Wednesday, January 23, 2008

### Scribes and Math Writing

Please read the first few pages of the Knuth, Larrabee and Roberts book on Mathematical Writing [PDF] before starting to type up the scribe notes: the list of dos and don'ts is particularly useful to look over...

## Tuesday, January 22, 2008

### Lecture 3: 1 vs. 3/4 + eps hardness for Max-Coverage: now with bonus endgame calculations

Any questions about the lecture can go here. I'll also show how to finish off the calculations.

First, there was one small extra idea that I didn't have time to mention: It uses the fact that the function $1 - 2^{-t}$ is a concave function of $t$. Recall that the overall average number of suggestions per edges is $2$. We also know that edges with t total suggestions but no consistent suggestions have coverage at most $1 - 2^{-t}$. We want that they have overall coverage at most $1 - 2^{-2}$. We need to check that the Suggester can't "cheat" by achieving awesome coverage on some edges by "spending" a lot of suggestions, overcoming bad coverage on edges where few suggestions were spent.

This indeed follows from concavity. As an example, suppose the Suggester is labeling 2 edges inconsistently, and it has 4 labels to spend (average of 2, as needed). It could spend 2 on each and achieve avg{$1 - 2^{-2}$, $1 - 2^{-2}$) $= 3/4$. Or it could try spending 3 on one and 1 on the other. But this only achieves avg{$1 - 2^{-3}$, $1 - 2^{-1}$} = avg{7/8, 1/2} $\lt$ 3/4.

With that idea noted, we come to:

Formal endgame of proof:

Define an edge $(u,v)$ to be "frugally suggested" if $|Sugg(u,v)| \leq 10/\epsilon.$ Next, define an edge to be "good" if it is both frugally and consistently suggested.

Suppose the fraction of good edges $(u,v)$ is at least $\epsilon/20$. We argue that this implies E$[val_{\mathcal{G}}(f)] \geq \eta = : \epsilon^3/2000$, as desired. Supposing $(u,v)$ is good, it has consistent suggestions and hence there exist $a \in Sugg(u)$ and $\alpha \in Sugg(v)$ such that the labeling $(a, \alpha)$ satisfies the constraint on $(u,v)$ (that is, $\pi_{v \rightarrow u}(\alpha) = a$). Further, since $(u,v)$ is good, it is frugally suggested, so both $|Sugg(u)|$ and $|Sugg(v)|$ are at most $10/\epsilon$. Thus when $f$ is randomly chosen, there is at least an $(\epsilon/10)^2$ chance that it will get both $f(u) = a$ and $f(v) = \alpha$, thus satisfying $(u,v)$. Hence in expectation, $f$ satisfies at least an $(\epsilon/20)(\epsilon/10)^2 = \eta$ fraction of edges $(u,v)$, as desired.

It remains to show that indeed the fraction of good edges cannot be less than $\epsilon/20$. If this were the case, then for a randomly chosen edge $(u,v)$,

P$[(u,v)$ consistent suggestions$]$

## Monday, January 14, 2008

### Lecture 1: Definitions; greedy algorithm for Set-Cover & Max-Coverage

Any questions or comments about Lecture 1 can go here.

I also wanted to include just a little bit of my own opinion on why studying approximation algorithms is worthwhile.

The "usual" motivation given is the following: In practice we are faced with NP-hard problems, and we nevertheless want to do something besides just give up. This is definitely true. The motivation suggests that running an approximation algorithm is a good idea -- they have worst-case performance guarantees! This is partly true, but it's not the whole story.

As an example, at one point in late 2001, the best known approximation algorithm for "Uncapacitated Metric Facility Location" (sounds complicated, but it's actually a very natural problem studied in industry; we'll discuss it later in this class) was a 1.73-factor approximation [Guha-Charikar]. It used an unholy combination of linear programming, primal-dual methods, and greedy methods. It's doubtful anyone ever ran it. At the same time, there was a relatively simple, quadratic time greedy algorithm achieving a 1.86-factor approximation [Mahdian-Markakis-Saberi-V.Vazirani]. One would be hard-pressed to say that the 1.73-factor algorithm was a better heuristic in practice for the problem. (The current best known algorithm is 1.52-factor [Mahdian-Ye-Zhang] and is combinatorial.)

On the other hand, take Set Cover. Even though we know that the Greedy algorithm only achieves somewhat bad performance -- a ln n factor -- we would and do run it anyway.

So breakthroughs in the analysis of a problem's approximability don't necessarily help you out at all in practice.

(I should emphasize, though, that sometimes they do: for example, the Goemans-Williamson .878-factor Max-Cut algorithm has had a huge impact on practice; not because it is a .878-factor approximation algorithm but because it gave powerful evidence in favor of an algorithmic technique (semidefinite programming) which is today a key component in practical Max-Cut algorithms.)

Regardless of the "heuristics for practice" motivation, there are additional reasons to study approximability:

1. It helps you understand "hard instances"; for example, what properties of Set-Cover instances make them hard? What properties make them easy? Studying approximation algorithms for the problem usually reveals this and helps you design algorithm for special cases. See also Luca Trevisan's opinion on the whys of approximation algorithms.

2. It tells you something about P vs. NP. (This is my person reason for studying approximability.) Take Max-Cut for example. We know that .878-approximating it is in P. We also know [Håstad-Trevisan-Sorkin-Sudan-Williamson] that .942-approximating it is NP-hard. What about the algorithmic problem of .9-approximating Max-Cut: is it in P or is it NP-hard? No one knows. In fact, experts have contradictory guesses. And this is for Max-Cut, which I'd argue is the simplest possible NP optimization problem. How can such a simple problem evade being classified as being in P or NP-hard? I find this to be an even more galling situation than the unclear status of Factoring (which most people at least guess is not in P) and Graph-Isomorphism (which most people at least guess is in P).