Thursday, March 3, 2011

Dagstuhl Thursday fatigue

With tutorials to ponder, open problems to think about, and a paper to work on while my coauthor and myself are in the same place, my interest in talks has waned, and most of it is going above my head while I am taking stock of what I learned during the first three days of the workshop. I have therefore changed my seat, farther from the board and closer to the window where I can bask in the sun and enjoy the view.

Something during this morning's tutorial caught my attention, though.
- Baruch Schieber: "This notion that you use in your proof, I call it the red point's shedow."
- Magnus Haldorsson (the speaker), puzzled: "Shedow? Is that yiddish?"
- Person in audience: "No: when you hear him say "shedow", he really means "shadow"."
I am so glad that someone else has an unapologetically strong accent in spite of having lived in the US for many years! I am grateful for the tolerance of Americans for us immigrants with our imperfect English. They realize that the simplified English that we use in our international interactions is the modern Esperanto.

I also listened to Seffi Naor's tone during his talk. His voice goes up and down gently like ripples lapping the sea shore at night after the wind has died down. It is a pleasant, soothing sound. The content is surely very interesting (the title contains the exciting terms "small set expansion"!), but I am out of energy, and the long introduction listing previous work tried out my patience and quickly wore it out.

Obviously, other people are more resilient than me: they are still participating actively, asking questions during the talks. I don't know how they manage it!

Wednesday, March 2, 2011

Dagstuhl, Wednesday afternoon

The traditional Wednesday afternoon hike took us to a chapel where one could view Dagstuhl from a distance. During the hike Daniel Marx gave me a lightning-speed overview of techniques for FPT algorithms - one example for each algorithmic technique. Now, whenever I see an FPT algorithm, I will remember the sun-filled scenery of green hills, quiet ponds and small streams! David Johnson thinks that, rather than studying this or that more or less artificial theoretical model, our research time would be better spent trying to understand why integer programming works so well. He's had good experiences with it recently. I liked the idea. Neal Young criticized my wish to go back to the Plotkin-Shmoys-Tardos paper and try to understand it: now that I have heard his tutorial, I no longer need to read that paper, he says! (Except for examples of applications). Etc. This is why hiking is such a good thing to do during workshops. The blood flow stimulates the brain, conversation flows easily, and, in a natural environment, informal discussions on topics related to research happen in an organic manner.

The traditional stop of Dagstuhl hikers at a restaurant for coffee and cakes no longer exists. The reception tried to make a reservation for us, but got turned down. Rumor has it that, once, an order of seventy cakes was placed for one group, but nobody showed up at the restaurant. Since then, as the story goes, neighborhood restaurants refuse to take reservations for Dagstuhl people.

I also broke with tradition at meal time: I arrived early, found that Kirk Pruhs and I were going to be seated at the same table for at least the fourth time in a row, and quietly exchanged his name tag with one on the next table. When Kirk arrived, a few minutes later, he took a look at me, at the name tags, and commented: "Not today, eh?"

I have made one convert to tablets: Samir Khuller. He started using his yesterday to take notes during talks (had had it for a while but had never used the tablet features!). Today he asked me how to share a document with other people on the internet, so that we could all edit it at the same time. That would obviously be extremely useful for long-distance collaborations. One would think that that has to exist - the technology is there, there is no reason why that shouldn't be possible. But I don't know.

Dagstuhl, Tuesday afternoon and Wed morning

The afternoon talks were somewhat less well attended, because the weather is so beautiful that some people just can't resist the sun and stay outside beyond the specified time.

Baruch Schieber talked some more about busy time problems. He spent some time on motivation. It's about having the minimum number of computers turned on, so, like in Kirk Pruhs' talk, it's also about minimizing power usage. It would have been nice if his talk had been before Samir's talk!

Lisa Fleischer talked about flows over time. I have heard talks about this several times, but this was the first time that I understood the problem definition before the talk was over. There's a picture of a pitcher pouring some red or blue stuff into the network. Actually, the rate at which it is pouring matches the maximum "capacity" of the edge on which things start. Also, I always think of "capacity" as a static quantity, but in this setting it's actually a rate- say, the maximum rate at which a highway can route cars without getting jammed. And time, as well as the stuff being routed, are all continuous quantities. Capacity reduction can help increase the flow. I keep thinking of those lights that regulate the rate at which cars can enter the acceleration ramp on highways at rush hours in the US. Those lights don't exist in France. I think that the French, being rational people, would not believe that you can get better overall flow by reducing input, and would therefore ignore such traffic lights. But in the US people are law-abiding enough that they stop at red lights even if it seems unreasonable.

Leah Epstein talked about online clustering problems in one dimension.

Asaf Levin talked about an asymptotic fully polynomial PTAS for bin packing with various bin sizes and costs. The techniques were a bunch of rounding/shifting/DP stuff, but the result was surprisingly strong!

In the evening we had an open problem session in the cheese room. I can't say that there was one problem that really captured my fancy, but they varied from puzzle-like to broad and ambitious questions. Then there was mafia, bridge, beer, wine, poker, and even one of the open problems was solved along the way! By a PhD student, of course: only they have the stamina to continue working at the close of the day. I noticed several people were wearing slippers.

Wednesday morning Neal Young gave a black board tutorial on Lagrangian relaxation and presented one algorithm applied to several different settings. Now it seems that I might finally be able to go back and read the Plotkin-Shmoys-Tardos paper, and it might even be easy. We'll see. Then Grigoriadis talked about non-linear approximation.

Dagstuhl, Tuesday morning

Ola Svensson gave two talks about hardness of approximation for job shop and (unique games dependent) hardness of precedence-constrained scheduling on parallel machines. The reductions were simple and we had a black-board talk, so that we were able to follow (almost) everything. What a great pleasure! I love slow talks. Otherwise I cannot listen to 5 hours of talks a day. I showed off how to use a tablet - borrowing someone else's tablet and writing notes for the talk, that will be uploaded to the Dagstuhl website shortly, so that everyone can use them as if they were the slides for the talk.

Niv Buchbinder gave a linear-programming approach to the secretary problem and variants. Let pi be the probability that the ith arrival is hired, qi be the probability that he is hired given that he is the best of all, fi be the probability that he is hired given that he is best aong the first i. Since the problem is online, qi=fi. We can write a few constraints that must be satisfied, then a feasible solution suggests an algorithm, and exhibiting a matching dual feasible solution proves optimality. Simple and classic LP approach to online problems, that nicely unifies several s of the secretary problem. Elegant. Open: take that approach for the knapsack variant.

Before talking about the underlying LP, Niv started by showing an algorithm, then had to fight a rebellion from the room: he wanted to move on to the analysis, but instead was attacked by rapid-fire questions, all of which he answered with: "Wait, it'll come in a couple of slides!" - a good teaser talk. Fun!

Monday, February 28, 2011

Dagstuhl - Monday afternoon

The theme of the afternoon: FPT-type algorithms.

Daniel Marx gave a survey talk on FPT and approximation algorithms. Very interesting for me, because it is very close to my research area even though I have not been following what was happening. There are lots of results coming out, and some of them seem quite clever. Most of the results he mentioned were for optimization problems on graphs. Unfortunately there were almost no proofs, but the ingredients, according to his keywords, seems quite close to techniques for approximation schemes.

Why are FPT results interesting? One reason: because they seem to give some insight into the structure of those basic problems; at least, that's my impression, although, without an actual detailed proof, it's kind of hard to tell. Another reason: because they can conceivably lead to actual implementations. But Daniel was kind of vague about that; it's not the direction in which his personal interests are taking him, and I am maybe with the wrong crowd this week to get a good answer to that question. (One might also wonder: why do I, a pure theoretician, care?) Certainly, the area seems to be taking off these days.

Klaus Jansen and Ildi Schlotter both talked about the most famous bin packing/cutting stock problem: is there an approximation algorithm with additive approximation +1? Klaus talked about the special case where there are only a constant number k of distinct item sizes, and Ildi talked about the special case where there are only a constant number k of bins available, and their runtimes were of the form f(k)*poly(input size), where the polynomial was independent of k: in that sense, their algorithms were FPT-type. Because of the famous open problem driving research in that area, I did not need further motivation, so I was pretty interested in those results. After that I had had enough and skipped the last talk of the day.

How not to do research

(1) Fix a deadline (say, 3pm).
(2) Wait until time gets short (say, 2pm)
(3) Make a plan to get to your goal (say, a chapel on a hill with a view)
(4) Get going according to your plan (say, on a bike)
(5) Keep going even though you are suspecting you may have missed your goal, just because continuing on the uphill road, even though it's work, require less thought than getting out your map and reconsidering your plan in more detail.
(6) Once you run out of time, you are eventually forced to stop and wonder whether you were just being stubborn. With the additional knowledge you gained along the way, it is immediately apparent that you went the wrong way a long time ago - and that, had you stopped much earlier, things would already have been clear and you would have saved yourself a lot of pointless effort. Moreover you now have a much better idea of what the right way is.
(7) By that time it is too late to go there in time, so you just give up altogether.

Dagstuhl - Monday morning

I'm attending a Dagstuhl workshop on scheduling etc. This morning we had three talks. The main theme seemed to be defining new scheduling problems.

Kirk Pruhs talked about green computing. To conserve energy, current architectures have heterogeneous processors, so scheduling with related machines are problems of current interest. Speed-scaling is also of interest. The problems sucessfully studied in that realm seem to have mostly straighforward algorithmic solutions, and the theoretically interesting part is in the analysis rather than in the design. The main open question currently is to define "good" problems.

Samir Khuller talked about busy times minimization. Busy times are times when at least one processor is active. Thus one tries to schedule jobs simultaneously as much as possible, given various traditional scheduling constraints.

Tami Tamir talked about bullying. Replace the usual notion of precedence constraint (job j can only start once job i has finished) by "bullying" precedence constraints (job j can only start once job i has started), and study various traditional scheduling problems when one adds this new type of constraints.

Maybe I'm blase, but so far I have not seen a problem that I'd like to work on or a result whose proof I' am curious to understand in depth. It would be nice if the speakers could formally define a nice, compelling open problem, even if that problem is beyond our reach at present. What is driving the field? Is there an open problem whose answer would be a breakthrough, and why? That'll be my question for our session on the future of scheduling.

Sunday, February 27, 2011

Life as a professor

Occasionally a student asks me diffidently: "So, when you are not in the classroom teaching... what exactly do you do? I understand that class preparation takes a lot of time. Do you also do, like, research?"

Here is a list of the kind of things I do (or feel guilty about not doing) at work.

Preparing lectures, giving lectures, writing lecture notes, holding office hours.
Meeting TAs, preparing (or helping to prepare) assignments, grading (or helping to grade) assignments.
Advising undergraduates.
Attending faculty meetings, doing department committee work and university committee work.
Organizing workshops and conferences.
Journal editor work, Conference program committee work.
Reviewing conference submissions.
Reviewing journal submissions.
Writing recommendation letters at various levels.
Applying for grants, writing grant reports.
Preparing talks, giving talks, traveling to give talks.
Attending seminars, workshops, conferences; traveling there.
Reading paper, just for the sake of learning.
Meeting with students and research collaborators to do research together.
Writing conference papers.
Writing and revising journal papers.
Reading, processing, sorting email.

That is more than full time, so some things end up not getting done. For example, I almost never read a paper just for the sake of learning.

My favorite activities by far: meeting other people to discuss research, and lecturing. Because those activities form the core of this profession, it is my impression that it is a good profession for me. However it also requires managerial skills that I just do not possess, and that tends to spoil my life.

Thursday, February 17, 2011

More raving about tablets

I find myself using the tablet more and more.

I have started using it as a substitute, not just for a black board, but also for paper. When I meet with students in my office, we write on the tablet. Here are some immediate advantages:
- from one meeting to the next, I can recover my notes from the previous meeting. It saves us from having to write notes or finding my loose sheets from the previous meeting. It's a good antidote to my lack or organization. Some people have a different notebook for each research project: the tablet is the digital equivalent
- pens of all colors are readily available (whereas, when I use pen and paper, I seldom have more than a few colors at my disposal)
- ability to send my collaborators the current file at any time
- as we discuss problems, often we want to change the order of the argument. When you say "oh, we should have defined x before doing this operation", on paper it requires an ugly margin addition; when these modifications accumulate, it becomes unreadable. Whereas, on the tablet, it's easy to move things around or to create an extra page. At the same time, it does not distract me from thinking about the problem we're discussing (in the way a standard editor would).

I am currently working on a paper and it seems to help organize our thoughts and our writing. Often the arguments of a proof come in the wrong order, or are mixed up, perhaps with algorithm and analysis discussed all together, or defining an object and proving things about it simultaneously (as happens when one is developping ideas), and then one needs to separate them cleanly for a rigorous and clearer writing. On a tablet that can be done by moving objects with the stylus.

The other day my son had a question about his Math homework, and I got out the tablet to explain it to him!

The only advantage of pen and paper over the tablet are the physical constraints: using a tablet requires having a tablet. It's heavy, it diffuses heat, and it needs to be plugged in after a short time.

I read that many are dubious about the stylus and do not consider it a good invention, but, in my view, using a finger instead of a stylus is like using fingerpaint instead of a paintbrush.

Tuesday, February 15, 2011

Glimpse of another life

Overheard today on the bus: "I'm not going there alone. I get scared when I am alone!" - coming from a grown man, in his fifties, chatting with his neighbors.

That caused my brain to go into "Something's not normal" mode. I took another look at him and at his two neighbors. I noticed similar jackets and similar hats. I then imagined that they might be special needs adults living in a group home. Pure, hasty speculation - but why else would a grown man say that he gets scared? Since my stop was coming up, there was no time for me to figure things out, so I don't know.

Had it been a child or a woman, I would not have noticed. But for a man, in our society that kind of language is taboo in public.