Computational Complexity

Wednesday, November 30, 2005

 
The Graduate Complexity Course

Posted by Lance

After my post on teaching PCPs, a reader questioned the wisdom of spending 6-8 lectures on PCP and asked what topics should be taught in an introductory graduate complexity course. This is not a new issue. In the spring of 1985 I took a graduate complexity course with Juris Hartmanis at Cornell and in the spring of 1986 took a graduate complexity course with Michael Sipser at Berkeley with only the polynomial-time hierarchy in the intersection of the two courses.

Here is my list of the topics and theorems that should be covered in a graduate complexity course. Depending on the school, some of this material is covered in undergraduate courses. More material should be added based on the interests of the instructor.

• DTIME(f(n)) ⊆ NTIME(f(n)) ⊆ DSPACE(f(n)) ⊆ NSPACE(f(n)) ⊆ ∪_cDTIME(c^f(n)).
• Basic time and space hierarchies.
• NSPACE(s(n))⊆DSPACE(s²(n)) and NSPACE(s(n)) = co-NSPACE(s(n)).
• The P versus NP problem and NP-completeness. SAT is NP-complete.
• The polynomial-time hierarchy.
• Alternation (Alternating polynomial-time = PSPACE).
• Probabilistic Complexity Classes (BPP, RP, ZPP). BPP ⊆ PH.
• Counting (PH ⊆ P^#P).
• The PCP theorem. Even if you don't do the proof, state the theorem and the implications for hardness of approximation.

9:12 AM #

Tuesday, November 29, 2005

 
Game Theory Finds Computer Science

Posted by Lance

Dear Game Theorist/Computer Scientist:

In keeping with our mission "to facilitate cross-fertilization between theories and applications of game theoretic reasoning," Games and Economic Behavior has decided to expand its publications of papers in the interface of game theory and computer science. To this end, we are pleased to announce that the following individuals have accepted our invitation to join the editorial board:

• Joseph Halpern, Cornell University
• Michael Kearns, University of Pennsylvania
• Noam Nisan, Hebrew University
• Christos Papadimitriou, University of California at Berkeley
• Moshe Tennenholtz, Technion - Israel Institute of Technology

Submitted papers will be subject to the journal's high standards of evaluation. In particular, they must be of interest and must be readable to researchers in other fields. Given the differences in the publication processes of different fields, GEB is not opposed to publishing expanded versions of papers that were originally published in conference proceedings (provided they satisfy copyright law).

We hope that you see GEB as a venue to reach a broad group of readers for your publications.

Sincerely yours,
Ehud Kalai
Editor GEB

4:16 PM #

Sunday, November 27, 2005

 
Chess and Poker

Posted by Lance

Two very different articles in today's New York Times about battling the decline of interest in Chess. In the Op-Ed section, Jennifer Shahade, a recent US women's chess champion argues that chess should learn lessons from Poker.

How can chess save itself? No doubt it would make purists protest, but chess should steal a few moves from poker. After all, in the past few years, poker has lured away many chess masters who realized that the analytical skills they've learned from chess would pay off in online card rooms.

And that's a shame. There are plenty of smart people playing poker (and I love playing it myself), but there's no denying that when it comes to developing mental acuity, chess wins hands down, so to speak. Dan Harrington, a former world poker champion who quit chess because there wasn't enough money in it, laments that poker is thin and ephemeral in comparison.

Meanwhile in the Style section, Dylan Loeb McClain discusses the World Chess Beauty Contest which has the stated goal of raising interest in the game.

Why has chess been undergoing a decline in interest in recent years? Perhaps after Deep Blue defeated Kasparov in 1997 the world views the best chess player as a machine, reducing interest in the game for humans.

And we shouldn't lament poker so. Prime time coverage of a game that uses probabilities, Bayesian analysis and complex strategies can't be completely a bad thing.

8:30 PM #

Friday, November 25, 2005

 
Goodbye Computing Chris

Posted by Lance

Chris Leonard, Elsevier editor of the CS theory journals is leaving Elsevier to be head of communities of the digital music service Digimpro. Theory loses a friend in Chris who talked with many of us about our Elsevier concerns and ran his own weblog at Elsevier (and will continue blogging at a new site). Chris helped push through the free year of Information and Computation.

As he leaves he presents his list of important aspects of the "perfect" CS journal. Many good ideas to think about, though we need to ensure a proper peer review of every journal article.

Thanks for your work for our community Chris and good luck in your new career.

3:01 PM #

Wednesday, November 23, 2005

 
Teaching PCPs

Posted by Lance

Two years ago for the first time, I gave the proof of the PCP (Probabilistically Checkable Proof) theorem in my graduate complexity course. The result, first proved by Arora, Lund, Motwani, Sudan and Szegedy, shows that every language in NP has a proof where a randomized verifier requires only a logarithmic number of coins and a constant number of queries to the proof. The result has helped show hardness of approximation for a large number of optimization problems.

I worked off of Mahdu Sudan's lecture notes and spent 8 fifty-minute lectures and still required a considerable amount of hand waving.

This year I used slightly less than 6 fifty-minute lectures with much less hand-waving based mostly on Irit Dinur's new proof of the PCP theorem. The six included a lecture by Jaikumar Radhakrishnan on expander graphs on a day I was out of town. I departed from Dinur's writeup in two ways:

• I used Radhakrishnan's version of Dinur's gap amplification argument.
• I used the proof that NP has a PCP using a polynomial number of coins and a constant number of queries in Sudan's notes (Lecture 3, Part II) instead of the long-code test in the appendix of Dinur's paper.

With experience I should be able to cut the number of lectures to five and the expander graphs lecture will help with many other theorems in complexity, not the least of which is Reingold's construction putting undirected graph connectivity in logarithmic space.

If the students already know expander graphs, the proof takes half as much time as before. Thanks Irit. But still that one lecture proof of the PCP theorem remains elusive.

12:26 PM #

Tuesday, November 22, 2005

 
Complexity Deadline Approaching

Posted by Lance

The December 4th paper submission deadline for the Computational Complexity Conference in Prague is fast approaching. Get your papers ready.

Other deadlines: Computational Geometry (Abstracts Nov. 23), Electronic Commerce (Dec. 6), COLT (Jan. 21), ICALP (Feb. 10), SPAA (Mar. 6). Leave a comment if I left out your favorite conference.

The accepted papers for STACS and LATIN have been posted.

10:51 AM #

Monday, November 21, 2005

 
Introducing a Speaker

Posted by Lance

When a scientist visits another university to give a seminar, someone gets assigned as host who during the talk introduces the speaker, makes sure the talk doesn't go too long and the post-talk questions don't get out of hand.

So how do you introduce a speaker? I've seen everything from "Let's start" to a reading of the speaker's CV. A few memorable ones (names have been changed):

• Jane Smith needs no introduction so I'll introduce myself instead…
• Last week we had a terrible talk on ABC, today we will learn whether it was the speaker or the area.
• John Doe is famous for proving the XYZ theorem. Today he will talk about something far less interesting.

Often the host gets much more anxious about the introduction than the speaker does about the talk. The host worries the speaker will get insulted if given the wrong introduction. Just find a couple of nice things to say and you'll be fine.

Don't ask the speaker how he would like to be introduced, as it puts the speaker in an awkward position. Last time my host asked me, I suggested he introduce me as "The person who put the 'W' in AWPP," but he didn't bite.

10:42 AM #

Saturday, November 19, 2005

 
Another Satisfied Customer

Posted by Lance

You attend the University of Chicago for three years, take a few years off and come back to finish your Bachelor's degree in Chemistry. You worked really hard to get that degree but you have trouble finding a job afterwards. What do you do? How about setting small fires in a number of University of Chicago buildings including the elevator in Ryerson Hall, home of computer science.

Luckily no one was hurt and there was very little property damage. Thanks to Nita Yack, our department administrator, and others who quickly put out the fire before it caused any real damage. Thanks also to the university and Chicago police who quickly caught the culprit.

6:42 AM #

Thursday, November 17, 2005

 
Relativized Collapse of P and NP

Posted by Lance

When we teach relativization, we often ask the class for a set A such that P^A=NP^A. The usual answers we get are an NP-complete A (which doesn't work unless the polynomial-time hierarchy collapses) or a PSPACE-complete A which does work: PSPACE ⊆ P^A ⊆ NP^A ⊆ NPSPACE = PSPACE the last equality by Savitch's theorem.

According to Steven Rudich, a student at Carnegie-Mellon suggested using A=K, the halting problem. Does this work? This led to an interesting email discussion between Rudich, Richard Beigel, Lane Hemaspaandra and few more of us getting cc'd on the messages.

We need to use a reasonably dense encoding of K, such as the set of Java programs with no input that halt. Then in fact P^K does equal NP^K, but the proof is not as obvious as one would imagine. Think about it.

And if anyone knows the original reference to P^K=NP^K, let us know.

7:58 PM #

Wednesday, November 16, 2005

 
Cornell versus Intelligent Design

Posted by Lance

As a Cornell University alum I get the occasional email from the president talking about the great things going on on the Ithaca campus. Today's email I received from Hunter Rawlings, the old president who's minding the store while the university finds a replacement for Jeff Lehman.

This strength and stability of purpose allowed me to use this year's state of the university speech to address a matter I believe is of great significance to Cornell and to the country as a whole, a matter with fundamental educational, intellectual, and political implications. The issue in question is the challenge to science posed by religiously-based opposition to evolution, described, in its current form, as "intelligent design."

This controversy raises profound questions about the nature of public discourse and what we teach in universities, and it has a profound effect on public policy.

I believe the time has come for universities like Cornell to contribute to the nation's cultural and intellectual discourse. We must be willing to take on a broader role as defenders of rational thought and framers of discourse about culture and society. In this spirit, I have asked our three academic task forces, on life in the age of the genome, wisdom in the age of digital information, and sustainability, to consider means of confronting the following questions: how to separate information from knowledge and knowledge from ideology; how to understand and address the ethical dilemmas and anxieties that scientific discovery has produced; and how to assess the influence of secular humanism on culture and society.

Makes me proud to see my alma mater taking a proactive approach to this important debate.

5:57 PM #

Tuesday, November 15, 2005

 
The History of RAM

Posted by Lance

Janos Simon gives a history of RAMs expanding on my recent Favorite Theorems post.

A single paper is like a snapshot of the state of research at one point in time. Research itself is a dynamic, changing, live stream of results and ideas, and a single snapshot often cannot do justice to the richness of the topic. The RAM paper is an excellent summary of definitions and problems, and worth reading today, but, at the time, it seemed to me more like a crystallization of concepts that were "in the air" and a clear and precise summary of important known questions rather than trailblazing exposition of new ideas. The theory of RAMs is fascinating, and I'll try to summarize some of the relevant work that preceded Cook's.

The RAM formulation dates back to von Neumann (after all the "von Neumann architecture" IS a RAM). von Neumann uses the RAM formulation to derive instruction counts for some programs for his first computer. So "unit cost RAMs" were well known from the beginning of computers, and counting the number of operations was known to be important. Knuth was a very strong advocate of the idea of analyzing the running time of algorithms using instruction counts: the first edition of the first volume of The Art of Computer Programming is from 1968.

Theoreticians interested in computability theory have published extensively on RAMs: an example of an early paper is Sheperdson and Sturgis JACM 1963. It has a bibliography of earlier work. These papers came from two different motivations: one was to find further examples of formalisms equivalent to Turing machines, as a kind of experimental evidence for Church's Thesis (see the book by Brainerd and Landweber for an exposition of a few dozen formalisms—Markov Algorithms, Post Systems, λ-calculus, and so on). The other was to find "better", more realistic theoretical models for real computers.

For example, one of the novel features of the ENIAC was that the program actually resided in the computer's memory (as opposed to outside fixed set of instructions as in the earlier Harvard Mark machines). Much was made of this feature of "stored program" that allows for the program to use itself as data and modify itself on the run, something that was judged to be "good for AI." Of course, the existence of a two-state universal Turing machine is a clear illustration that at a fundamental level of computability there is no difference between "hardware" and "software". Still, there was a great deal of interest to model such "ease of programming" features at a theoretical level. For example, Juris Hartmanis has an elegant result showing that there is a function that can be computed faster on a RASP (random access stored program machine) than on a RAM (Math Systems Theory, 1971).

So "RAM complexity" was alive and well. What made things confusing was that fixed length register RAMs are uninteresting, but if one allows unbounded length registers, it is unclear whether unit cost is a realistic measure, and, if not, what would be reasonable. A natural option is to charge for the length of the register that is effectively used, the log of the value stored. Of course, there is the problem that determining the complexity of an algorithm becomes even harder. Even peskier questions appear if one asks whether addition and multiplication should have the same cost, and if not, should one use the schoolbook (quadratic) cost, or perhaps the Sconhage-Strassen cost? Most researchers opted to use the unit cost, and avoid all these complications.

To make things worse, many algorithms in optimization are expressed naturally in terms RAMs with real numbers registers. Note that fundamental questions about this latter model are still very much open.

To summarize, measuring number of RAM steps as a complexity measure was not a novel idea. What made the Cook paper relevant was exactly the proliferation of RAM measure results. In particular the Stockmeyer-Pratt-Rabin vector machine paper (and the later Hartmanis-Simon multiplication RAMs) as well as RAMs holding reals used in the OR community made it important to be precise about the exact meaning of "number of RAM instructions" measure. The community was quite aware that logarithmic cost was polynomially equivalent to Turing machines, and these papers showed that unit cost likely wasn't. Cook and Reckhow wrote down precisely what was likely a kind of unwritten consensus among the researchers in the area. This was necessary and useful, but it did not "set the stage to make RAMs the gold standard". The stage was already set, people were using RAMs to analyze algorithms, and Cook and Reckhow was a precise and meticulous description of what this meant.

In short, if one wants a picture of what great things got started in the period, the paper is an excellent choice, but, as usual, the actual history is complicated, dynamic, and, I hope, interesting.

3:44 PM #

Monday, November 14, 2005

 
Acceptance Rates versus Competitiveness

Posted by Lance

The acceptance rates at conferences for theoretical computer scientists tend to run higher than acceptance rates at conferences in other areas of computer science. Does this mean that theory conferences are less competitive than their counterparts in other areas? In a word, no.

Researchers look at their papers and for a given conference, either feel they have a very good chance of acceptance, a possibility of acceptance or a long shot of acceptance and tend to submit only if their paper falls in one of the first two categories.

In non-theory areas like artificial intelligence, the committee must take a subjective look at the papers which means many more papers fall into the second "possibility of acceptance" category. Many more people therefore take the risk and submit their paper because they can't immediately put the paper in that third "long-shot" category. This leads to more submissions and a low acceptance rate.

For theory we do a much better job putting our papers into these categories, as we can self-judge the hardness of the results and have a good feeling of the importance of the results for the conference. Theorists can tell when their papers won't have much of a chance of acceptance and will, usually, not waste their and the program committee's time in submitting these papers to the conference. This leads to a relatively higher acceptance rate in theory conferences.

A similar analysis would also explain why the funding rates for the theory NSF program also tends higher than the funding rates at many other programs in CISE.

4:58 PM #

Saturday, November 12, 2005

 
The Enemy of the Good

Posted by Lance

Alice (not the real name) has a STOC submission with Bob and wanted to put the paper on a public archive. Bob insists that the paper not go public until the "exposition is perfect", which if taken literally means never. I told Alice about a phrase my wife liked to use

Don't let perfection be the enemy of the good.

I hesitate to write this post because we far too often have the opposite problem, authors who take their hastily written deadline-driven conference submissions and just put them out on the web in its messy state. But aiming for that impossible perfection in the exposition spends considerable time making tiny changes to an abstract that, in most cases, no one would have noticed. One can better spend their time in other ways, like doing research for the next paper.

So take a little time to clean up the conference submission but then don't worry about every little detail. As soon as possible make it available for all to see. If there are problems in the exposition, people will let you know (especially if you fail to cite their research) and you can fix the paper accordingly. Psychologically you will feel better getting that conference submission you had spent that hard concentrated effort on out of your mind, until it (hopefully) gets accepted and you have to work on the proceedings version.

7:48 AM #

Thursday, November 10, 2005

 
Favorite Theorems: Defining the Future

Posted by Lance

October Edition

We end the list of favorite theorems from 1965-74 with two seminal papers by Cook and Reckhow.

Stephen Cook and Robert Reckhow, Time-bounded random access machines, STOC 1972, JCSS 1973.

Stephen Cook and Robert Reckhow, On the lengths of proofs in the propositional calculus, STOC 1974, JSL 1979.

The first paper developed the random-access machine (RAM) for measuring the time complexity of algorithms. "Random" here has nothing to do with probability, it just means we can access the memory in an arbitrary order.

Up to that time the multitape Turing machine was considered the model of choice for complexity but one had to access memory in a sequential fashion. The RAM model allowed quick access to all memory and much more accurately captured how real-world computers operated that previous models. Most algorithms papers give their time bounds in the RAM model and RAM is the gold-standard for proving lower bounds.

The second paper had a more delayed effect on complexity. Cook and Reckhow formalize a proof system for Tautologies as a polynomial-time computable function f whose range is exactly the set of tautologies. If f(p)=φ, p is said to be a proof for φ. They show that NP=co-NP iff there is some proof system such that every tautology φ has a proof polynomial in the length of φ.

This suggests an approach to separating NP from co-NP (which would imply P≠NP): Show that tautologies cannot have such proof systems. In 1985, Haken showed that the pigeonhole principle, encoded as a tautology, did not have polynomial-size resolution proofs. This led to a very active research area on proof complexity that finds lower bounds for various classes of tautologies on different proof systems, though we still remain quite far from NP≠co-NP.

Paul Beame and Toni Pitassi have a nice though slightly dated 1998 survey on propositional proof complexity.

7:36 AM #

Tuesday, November 08, 2005

 
Negotiating Your Job

Posted by Lance

An excellent Chronicle article on negotiating your job offer. I fully agree with the article that you lose out considerably by not negotiating and that you focus more than anything else on salary. An extra $5000 now will grow through the years as salary increases are usually a percentage of the current salary. Universities try to hold down the salary for similar reasons.

Once a department makes an offer, even if it was a tough decision, they then try as hard as they can to get the candidate to accept. Losing a candidate looks bad in their university and in the CS community. Take advantage of this and negotiate hard. Remember that once you agree to a contract your negotiating power goes to zero and remains zero for years to come.

For computer science, the Faculty Salary section of the Taulbee Survey can give you some idea what kind of income to aim for.

After salary, try to negotiate larger startup (or individually money for summer salary, students, travel), course reductions and any special needs you might have. As a rule, anything is negotiable.

If you have two offers, even if one offer dominates the other you should keep both offers open to be in a better negotiating position. This isn't good for the community as it keeps two positions tied up, but you need to think about yourself. Try to wrap up the negotiations as quickly as possible though so you don't keep jobs away from other people.

And, of course, if you get an offer from Chicago, ignore all of the above and just accept our initial offer immediately.

3:13 PM #

Monday, November 07, 2005

 
Games for Girls

Posted by Lance

This notice came into my inbox last week.

ChicTech, an outreach program of the University of Illinois Department of Computer Science, extends an open invitation for college women to participate in the second annual Games for Girls Programming Competition (G4G).

G4G was conceived in response to research indicating that boys enjoy a relatively greater degree of confidence with computers because they spend more time as children playing computer games. The research suggests that this difference in confidence contributes to the gender imbalance seen in the field of Computer Science.

So the gender imbalance in CS is due to the fact that girls don't play enough computer games. Guess that makes me a bad father for limiting the amount of time my daughters spend on the computer.

I do see at least one of my daughters more confident talking anonymously in a virtual world than in her real classroom. So suppose we had some virtual classrooms where students were represented by avatars (cartoon characters) and nobody knew the mapping from real students to avatar. Then the women (and the men) might be more willing to participate if they felt they had no risk from speaking up. But is this the environment we really want to teach in?

8:03 AM #

Saturday, November 05, 2005

 
Bringing Complexity to Your iPod

Posted by Lance

Welcome to ComplexityCast, the first of a very occasional podcast, an audio version of this weblog. First up, Bill Gasarch and I talk about the P versus NP problem. Download the MP3 (3.4MB, 20 minutes) or subscribe to the Podcast Feed.

6:50 AM #

Friday, November 04, 2005

 
Whither to Compete

Posted by Lance

A guest post by Rakesh Vohra.

Fortnow's post on competitive ratio's has prompted a number to speculate on the `right' number of people who should engage in competitive analysis. I took Fortnow's post as an invitation to revisit the arguments in favor of doing this kind of analysis. As I see it there are four arguments:

1. The argument from beauty: Truth is beauty and beauty is truth. The first direction I buy, the second, except in the case of Grecian urns, requires a proof. In any case, I am prepared to accept the aesthetics (or wit, cunning) of competitive analysis as sufficient justification for engaging in competitive analysis. Perhaps competitive analysis is to CS what number theory is to Maths. There are, however, shared aesthetic standards (otherwise the criterion has no bite), so only some kinds of work can be justified in this way. My guess is that the analysis of problems that can be stated with a minimal of fuss, have an immediate appeal and seem simple in the first telling (pretty much what makes for a good number theory problem) meet this criteria. So, TSP, SAT, clique, coloring, max-cut are in. However, the stochastic, dynamic traveling dog and pony problem with piecewise linear costs is out.
2. The argument of fine distinctions: Not all NP-complete problems are alike. Some really are easier than others. Therefore one would like a device to make distinctions between them. The bounds from competitive ratios appear to do a nice job in this regard. Knowing that a problem can be approximated to within a log factor but not within a constant factor does tell us about its difficulty relative to others. Notice that order of magnitude of the ratio suffices for this purpose and not the best possible ratio.
3. The argument from ignorance: If we do not know what the distribution of problem instances looks like what choice do we have? The assumption of complete ignorance is an extreme one and can be justified in some but not all cases. If one adopts this justification for engaging in a competitive analysis one must first argue that the assumption of complete ignorance is reasonable to make. One can imagine natural situations where partial information is available. In these cases it seems reasonable to expect error bounds that incorporate such information. Bounds that are data dependent are not as pretty as ones that are independent of the data, but may be more useful.
4. The beneficial spin-off argument: This is the argument that Vazirani makes. Putting a man on the moon is a Quixotic task but we received non-stick frying pans as a by product. However, we might have had non-stick frying pans by focusing on non-stick frying pans and saved ourselves the trouble of putting a man on the moon. The point is that this argument does not rule out other ways of achieving the same benefits.

The arguments do not provide a universal defense of a competitive analysis but justifications to be used on a case by case basis. I think the question to be asked is this: if an exercise in competitive analysis cannot be defended on aesthetic grounds, reveals/verifies no new and novel distinction, inhabits an environment in which complete ignorance is an unreasonable assumption and has no identifiable beneficial spin-off, why is it being done?

Competitive analysis is now an export business. One of the areas it is being exported to is game theory. This raises a new problem not present in the clean optimization framework. That is, does the notion even make sense when what one is comparing are preferences rather than objective function values?

5:30 AM #

Thursday, November 03, 2005

 
Losing the Office Phone

Posted by Lance

About a month ago I had the phone in my office removed. The number was one digit off from both maternity and a nurse's station at the U of C hospitals and if you Googled "Chicago Ballroom Dancing" my office phone number came up. About 90% of the phone calls were wrong numbers and I had gotten to the point of not answering the phone unless I recognized the Caller ID.

I could have had the number changed but I spend enough time outside the office (at TTI, other universities, working at home) that calling me at the office was not a reliable way to reach me. So I just eliminated the office phone and put my mobile number on my home page and in the university directory.

I don't rack up lots of minutes; we are primarily an email-based community and I get on average about one work related phone call a week. I made the change not because I want to use the phone less, rather to make myself more accessible. Our community relies on email too much, there are sometimes the old telephone still comes in handy.

• Calendar coordination.
• Convincing someone to do something. It's much harder to say "no" on the phone than on email.
• Sensitive information. Email leaves an electronic trail and one little typo in the email address can send your scathing comments who knows where.
• Some people like to use the phone for research. I prefer email because it forces you to think about what to write and you get a record of the discussion. But if there is a technical point you disagree on, a phone call can often quickly resolve the issue.
• Handling a disagreement, particularly when one or both sides are emotional over the issue. This situation is even better handled in person, if possible.
• Catching up. At the end of a phone call we often talk about other things going on in our lives. Happens far less in email.

More and more of our community are beginning to use instant messaging for many of these purposes. Also with VOIP services like Skype becoming more popular, the rest of you might lose your office phones sooner than you expect.

6:57 AM #

Tuesday, November 01, 2005

 
Competitive Analysis

Posted by Lance

When you cannot achieve the optimum solution of a problem, how do you measure the performance of an algorithm? If you knew the distribution of instances, you can see how well the algorithm performs on average. But most theoretical computer scientists prefer a worst-case analysis that tries to minimize the ratio of the optimal solution to the algorithmic solution. But many algorithms achieve seemingly large ratios that don't seem practical.

Vijay Vazirani defends this competitive analysis of algorithms in the preface of his 2001 book Approximation Algorithms.

With practitioners looking for high performance algorithms having error within 2% or 5% of the optimal, what good are algorithms that come within a factor of 2, or even worse, O(log n) of the optimal? Further, by this token, what is the usefulness of improving the approximation guarantee from, say, factor 2 to 3/2?

Let us address both issues and point out some fallacies in these assertions. The approximation guarantee only reflects the performance of the algorithm on the most pathological instances. Perhaps it is more appropriate to view the approximation guarantee as a measure that forces us to explore deeper into the combinatorial structure of the problem and discover more powerful tools for exploiting this structure. It has been observed that the difficulty of constructing tight examples increases considerably as one obtains algorithms with better guarantees. Indeed, for some recent algorithms, obtaining a tight example has been a paper in itself. Experiments have confirmed that these and other sophisticated algorithms do have error bounds of the desired magnitude, 2% to 5%, on typical instances, even though their worst case error bounds are much higher. Additionally, the theoretically proven algorithm should be viewed as a core algorithmic idea that needs to be fine tuned to the types of instances arising in specific applications.

But still why should a practitioner prefer such an algorithm to a heuristic that does as well on "typical" instances but doesn't have a worst case bound? Our usual argument says that we don't really know what "typical" means and we can promise you something no matter what happens.

Besides approximation algorithms, theoreticians have taken competitive analysis into other arenas, like comparing on-line versus off-line job requests and auctions that make a constant factor of the optimal revenue where achieving a competitive factor of 2 can mean a serious loss of income.

Sometimes these algorithms will allow themselves to do poorly when the optimum is bad in order to achieve the best ratio. If we truly want to sell these algorithms to the practitioners, should we focus on doing well on the situations they care about and then, only secondarily, worry about the performance in the worst case?

8:43 PM #

Archives