19 March 2016

How I got much better

In the last 18 months, I stopped going to doctors and instead focused on self-experimentation. Many experiments failed, but overall it’s been a big success. Some symptoms are completely gone, some are still alive but few and far between, and some are thriving as well as for the last 15 years.

This post was supposed to be titled Living with histamine intolerance, part 4, but I don’t classify as histamine intolerant anymore. You can read parts 1, 2 and 3 to get better context, though.

Feel free to get inspiration from my experiments but remember that there are risks involved.

Life-style changes that worked

Sunlight

I always wondered why I felt better in the summer and worse in the winter. Each November my ability to exercise rapidly dropped, except when I spent autumn in sunny California and the symptoms were then postponed by two months.

I’ve tried spending every second in the Sun but it was very difficult to do in Sweden. Spending one week under the Arctic Sun didn’t do anything. Two days of kayaking helped a lot, but not as much as 3 hours of full-body sun bathing. Sunlight is the best cure against insomnia and bad sleep.

On the other hand, taking vitamin D in winter helps but doesn’t bring the full effect. It’s not so surprising, since sunlight does more to our skin than just vitamin D production and we’re only discovering those effects now.

Dietary changes

Diamine oxidase (DAO) is an enzyme that regulates histamine in our bodies. The only macronutrient increasing DAO concentrations in the intestinal lymph in rats is fat. In another study of rats, MCT oil increased DAO activity 2.5 times in the intestines.

Even though I’m not a rat, I had to try it out. Did it help? Maybe it did, maybe it didn’t. It’s true that my DAO levels are 3 times higher than before, but I have too little data to judge causality. An unexpected side-effect was a big decrease in headaches and migraines. This is perhaps not that surprising, since MCTs boost ketone production and ketogenic diets are therapeutic for a few neurological conditions.

The second big change in my diet was eating nose to tail – eating other parts of animals than just muscles. Organ meats are cheap, easy to cook and super-nutritious. Skin, bones and cartilage are rich in collagen, which seems to be beneficial for many. The nutritional wars concentrate too much on carbohydrates versus fat, while different proteins and amino acids are often ignored. That’s likely a big mistake.

I’ve changed other small things in my diet, but listing them all would need another full post. Luckily for you, someone made a nice infographic and wrote a book about my diet 4 years ago. After I found out about people copying my diet, I read the book and had a lot of Aha! moments. That being said, the book is overconfident at times and I’d be extra careful following their advice to the last word. Also check Scott Alexander’s critical review.

Probiotics

Abdominal pain has been my number one problem for years. I’ve consulted doctors and tried many things, but those brought minor improvements at best. With Lactobacillus plantarum, the pain was gone within hours. Bacillus coagulans was also helpful for better digestion, but I had to take it every day and was later able to achieve a superior effect with glycine-rich foods, so I stopped taking it.

While I swear by L. plantarum, I do believe that probiotics are mostly unnecessary. If you have to take them every day, there is probably a deeper problem that needs addressing.

Intermittent fasting

I’ve previously written about two stressors, cold showers and exercise, helping me cope with various symptoms. At about the same time I’ve started experimenting with another stressor: intermittent fasting. Surprisingly, fasted state is when I have the best focus and productivity. I usually skip breakfast and only eat within an 8–9 hour window, with a big lunch and a big dinner (or two).

Fasting is a stressor that requires caution, but an intuitive approach works well for me. When the body stops telling me “This is uncomfortobale, but I like it” and switches to “Are you trying to kill us?”, it’s time to listen and eat something.

Supplements

I don’t like using supplements, because I often forget to take them. However, they are a great tool for controlled experiments. For example, I’ve taken pure glycine for two weeks with great results and after that incorporated a lot of collagen into my diet (with the same results).

It’s all just placebo and correlation doesn’t imply causation!

If everything I’ve experienced is a placebo effect, where was it for the previous 4 years? Out of the 50+ lifestyle changes, prescription pills, supplements and probiotics I’ve tried, only about 15 worked. If there was placebo effect, it must have been negligible. However, the good ol’ regression to the mean (patients getting better on their own) definitely played a role. Then again, I’ve tried relying on it many times before and it was never sufficient on its own.

How do I know the interventions listed above helped? Either I’ve done sufficiently many experiments or the effect was so strong it’d be impossible to explain otherwise. For example, after taking nonsteroidal anti-inflammatory drugs (NSAIDs) regularly, strong abdominal pain started. Wikipedia lists gastrointestinal problems as the main adverse effect of NSAIDs and they are also known to disrupt gut flora. Nothing has helped me for years. Then one day I tried Lactobacillus plantarum and the pain was gone within hours. Fixing other stomach problems took another 10 months, but at least the pain was gone. Also, L. plantarum is one of the few probiotics that performs in medical trials on people and in other studies, animals benefited from probiotics after being given NSAIDs.

A true skeptic would say that correlation doesn’t imply causation and that such evidence is not sufficient. Many people don’t believe successful stories and dismiss any kind of evidence, often because it contradicts their beliefs.

Skeptics are right that no evidence is perfect and we can never be completely sure. I admit I didn’t use an identical twin as a control group and I didn’t double-blind my fasting experiments. However, my personal experiments showed that skeptics are as likely to be wrong as the people they criticize. I’m glad I didn’t listen too much to sites like QuackWatch and Science-Based Medicine, otherwise I would probably avoid probiotics, cholesterol and fat for no good reason.

The new skeptic movement reminds me of the disagreement between academic skeptics and Pyrrhonian skeptics 2 millennia ago in Greece. Academic skeptics claimed “Nothing can be known, not even this” while Pyrrhonians viewed them as too dogmatic. I’m siding with Pyrrhonians here and my advice is: be skeptical, especially of skeptics.

This post is getting too long, so let’s take a short break with classical music.



Self-experimentation and its risks

A while back my mom told me to drink a particular herbal tea to alleviate some of my symptoms. I replied with “If this herb was effective, it’d have performed well in scientific trials and doctors would have prescribed it to me.” The statement does make sense, but it involves many strong assumptions and often isn’t true.

As an example, there is a drug called ramelteon, which binds to the melatonin receptors and for all we know it has identical effects to melatonin and performs about the same as melatonin in clinical trials. A monthly supply of melatonin is about $5 while ramelteon costs $100, yet doctors prescribe ramelteon instead of melatonin. Or one time I asked a Swedish gastroenterologist about her opinion on L. plantarum and other probiotics. She told me I know more than her and I should keep trying. This is despite plenty of successful clinical trials, many done on Swedish universities.

The previous two examples were cures that proved themselves in trials. Using fat and MCT oil in particular to increase the production of DAO has only been tested on rats. Perhaps it also works on people, but as far as I know no experiment was done on people, so doctors wouldn’t recommend it.

Medicine seems to miss a lot of treatments, so self-experimentation might be worth it. It does bear a lot of risks, so I evaluated possible adverse effects and monitored my health. For example, I’ve closely monitored my cardiovascular risk factors and they stayed the same or improved. However, I don’t trust these tests completely. A comprehensive heart-disease blood test would include 5–7 different blood values, but despite so many numbers, its predicting power is limited. I believe that there is too much focus on lipoprotein particle size and soon a more important risk factor will be discovered, so I’m not pronouncing myself completely out of risk yet.

Blood tests are tricky to interpret for another reason. Some blood reference intervals are calculated so that exactly 95% people fall inside them and it’s not always clear if sick people are included or not (see here or here). Unfortunately, many doctors don’t know that and would diagnose you sick or healthy solely based on these arbitrary numbers. It reminds me of a TV discussion with someone complaining that poverty in the US has stayed exactly at 20% of the population for the last 100 years. This came as a big surprise, so the moderator asked about their definition of poverty. “It’s the poorest 20% of the population”, the first person said.

So I take blood tests and reference intervals with a grain of salt. Perhaps more important is tracking values over time and comparing them with a younger version of myself.
Disclaimer: While I don't have a lot of trust in medicine and doctors anymore, a world with doctors is much better than a world without them. Doctors are awesome at fixing anything acute or live-threatening. Next time I break my leg into six parts while skiing, I'm sure doctors will do a great job. It's the chronic conditions where my trust disappears.

Further reading

I recommend 3 blogs for anyone interested in health and medicine. And one crazy idea.
I’ve also read other websites and watched a lot of YouTube videos, but it’s a minefield that is very difficult to navigate. Especially nutrition discussions are often worse than politics or gender, with people citing facts out of context, ignoring evidence and sticking to dogmas. For example, many people benefit from vegetarian or low-carb diets and then preach them as the healthiest diets for everyone. Perhaps they are helpful in certain situations, but that doesn’t mean everyone should follow them or that they are safe in the long term. And some people don’t benefit from any diet, so they become radical skeptics and question everything. Usually there is some truth in each dogma, but some people take them too far.

Maybe this post is also full of untrue dogmas, misrepresented scientific findings and without contradicting evidence. Only time will tell. I tried to do my best, though.

09 December 2015

ELS: latency based load balancer

You might have noticed that the Spotify back-end has been faster by about 0.47 milliseconds in the last 6 months. Read about my new algorithm in two posts:
  1. The first one is simpler, has a lot of pictures, graphs and even three animations.
  2. The second one has all the necessary math.

24 November 2015

Swedish summer 2015

People said this was the rainiest Swedish summer ever, but I disagree. I slept 5 times in the Stockholm archipelago and each time without a tent. This is how we usually slept.

The best hotel in the Stockholm area. Cost: 0 SEK. Experience: priceless. At Angödrommen.
Maybe the weather was nice to me, since this was my last summer in Sweden. Stockholm archipelago, I'm going to miss you!

There is not much to write about all the trips I made, so let the photos speak instead. Don't continue if you are scared of swans, seals, mushrooms, spiders, snakes or dragonflies! A link to a full album is at the end of the post.

Finally getting dark at 11 pm
Swan family chose a vacation by the sea
Snake hiding in blueberries
Unknown water creature with many small legs
We thought we wouldn't be able to pass through at first. It turned out to be a channel made for kayaks.
Mirror sunset at Kolkböte
Happy people and happy sheep at Fjärdlång
Lonely mushroom
Dragonfly
We saw seals!
If you want to see even more wild animals, check the full album made from multiple cameras on Google Photos or a small selection of my photos on Flickr.

02 November 2015

Nordic championships in programming 2015: behind the scenes

Nordic championships in programming 2015 (NCPC 2015) took place three weeks ago and I was the head of the jury for the third time in a row, together with Markus Dregi from University of Bergen. Last year I’ve written my impressions from behind the scenes and I’d like to continue with the tradition. Let me first mention 2 problems that I liked.

H – Hero Power

Hero Power involved a simplified Guitar Hero game. On Tuesday September 29, about 10 days before the contest, the task still hasn’t been solved by anyone from the jury. Not even Björn had solved it, the author of the task who worked on it for a couple of months. In addition to many rules that were also present in the final problem statement, at the time there was an additional rule that the SP meter charges by extra 5 seconds at the end of every SP phrase (the so-called 5-second rule).

The contest was near, so me, Björn and Oskar decided to have a meeting on the sunny roof of Spotify’s office. We wanted to simplify the problem but it wasn’t clear how. I claimed that combining continuous charging with 5-second bonuses makes it hard to solve: when you draw the content of the SP meter as a function of time, you get a non-continuous function and such functions are hard to grasp. In this version, it’s not enough to charge in continuous chunks, because taking breaks allows you to collect just the right amount of 5-second bonuses. This complicated the solution greatly.

I suggested removing the 5-second rule but keeping everything else as it is. Björn disagreed. It was getting colder on the roof and we had music to stream, so we agreed to disagree. I wanted to ask the rest of the jury for opinions and also write a solution myself. Perhaps my modification wasn’t that elegant anyway.

After dinner I sat down to write a solution. It was an obvious dynamic programming problem, but the update step turned out to be very tricky. After about 30 minutes of thinking I finally got it and wrote a super-short solution. It felt too short for such a hard problem, so I proved its correctness 2 more times to convince myself.

I mostly liked lines between 41 and 50, which contain dynamic programming, greedy strategy and amortized complexity on a very small space. Even the preprocessing step is non-trivial and uses the ‘resize’ function in C++ ‘vector’ in an elegant way.

I had one of those rare moments when you are taken aback by a beautiful computer program. It was even more rare, since the code was mine. The problem version without the 5-second rule turned out to be awesome on many levels, so I went to defend it on our mailing list.
I've just implemented a solution for the version without the 5-second rule and I'm stunned. This is pure poetry! 
The task is a beautiful mix of dynamic programming, greedy, amortized complexity and clever data structures (just arrays and hash maps, but clever still). All the steps are non-trivial to make it run in O(np).
My excited e-mail was enough to convince everyone to remove the 5-second rule. In the end it was still very hard and only 2 teams solved the problem.

I – iCar

In this task you have an iCar with only one button – when pressed, the car accelerates with the rate of 1 meter per second per second. Once you release the button, the car stops immediately. (Side note: we have considered adding braking instead of immediate stop, but the problem was already too hard.)

This is yet another task that was shaped greatly with time and with the help of the rest of the jury (thanks a lot, Marc!). Andreas Lundblad sent us a suggestion already in May and it was basically the same problem as it appeared in the contest. He could only solve it for one semaphore, though. I managed to figure out all the cases needed to solve it for 2 semaphores, so I told him we’ll take the problem and figure out the details later. At worst we have the 2-semaphore version, but I was curious about extending it to 5 or even 100 semaphores.

In the end we went with 20-semaphore It was a lot of work and it took us a more than a month to get it right. First, Marc generated test cases, but my code was able to find a shorter route to the finish. Later, Marc found the nasty case shown below that broke my solution instead.

The crucial step in solving the problem is choosing the right visualization. There are two important parameters, the position of the car given in kilometers from the start and time since the start. The third interesting parameter is speed, but you can actually skip that and infer it instead.

Two parameters can be visualized in 2D: the picture below has time rising from bottom to the top and position from left to right. It contains a solution that illustrates all the different cases a correct solution needs to handle. Red vertical lines denote red lights on semaphores. Blue parabolas and dots denote a car that is accelerating and stopped respectively.
Solution to 000-random-seed-144.in. Marc also created visualizations for all test cases that you can download from the contest webpage. 
The second parabola is passing the 5th semaphore at the last moment of a green light and then passing the 10th semaphore at the earliest moment of a green light. We could have passed the 5th earlier, but we’d have to have lower speed to avoid hitting a red light on the 10th. This strategy allows us to pass the 10th semaphore with the highest speed possible.

While this might sound complicated, we're still not done and it's only enough to solve the 2-semaphore version. To solve the problem with 20 semaphores, you also need to handle two more cases, which are the last two parabolas in the picture.

The very high speed we acquired allows us to be at the 12th semaphore during a red light. We could stop at the semaphore and wait there for a green light, but a better strategy is stop earlier, so that we can start accelerating earlier and have higher speed when the 12th semaphore turns green.

Finally, we stop before the 13th semaphore and start accelerating, so that we pass it at the last moment of a green light. Such waiting strategy paradoxically improves the time in the finish. A little bit of calculus can prove that.

In the end no one solved the problem and I kind of expected that. One could argue that this problem should have been saved for a more difficult stage like NWERC or World Finals, but I’m not sure. Even small contests like NCPC need hard problems to stop the best teams from solving everything.

Overall this is one of the top problems I helped preparing for a contest, because quadratic geometry is very unusual in programming contests.

The bad

Apart from fun problems, a couple of things didn't pan out so well. Problem G was solvable with brute force if you managed to optimize it well. Problems D and E were too similar. Too many pproblems were dealing with time events.

We knew about these issue before the contest, but it was too late to change things. We already skipped some problems and were down to 10 when we discovered issues with G. Skipping one more problem felt like a worse decision than keeping it.

We could have prevented it if we received more problem suggestions and more people were helping out. If you would like to prevent similar situation from happening, please send problem suggestions next year. Don’t hesitate even if you aren’t skilled in preparing competition problems, because there’s always other jury members that can help you out. For example, Hero Power and iCar were suggested by people with little jury experience and then received a lot of help from the rest of the jury.

Conclusion

If you like the stories from behind the scenes, don’t hesitate to get involved next year! You can mail me at [polacek (at) kth dot se] and I’ll add you to the right mailing lists.

I’ve now left Scandinavia and after 3 years as a head of jury I’ve quit. I’d like to be involved though and contribute a problem or two next year. I hope the quality of NCPC stays very high!

29 August 2015

Underflow bug

Sometimes code needs to be executed 100 000 000 000 000 (100 trillion) times to hit a bug. Read my blog post for Spotify to learn more.

As usual, Reddit users were there to brighten my day:
  • "Really surprised such a successful tech company produced such shoddy code."
  • "This is remarkably shitty code. I would criticize pretty harshly anyone who wrote it. I would fire anyone who wrote a public blog post about it exactly like this post."
  • "So basic edge case failure. Not even a corner case."
  • "Yeah, not surprised that someone that thinks they invented the term underflow and used it wrongly got something like this wrong."
  • "[the code] is, pretty obviously, broken at a glance"

24 June 2015

Efficient Use of Exponential Size Linear Programs

After being sick on and off for a couple of years, I decided not to finish my PhD. I did write a small thesis, though. Thus on March 20, 2015, there were two big cosmic events: a partial solar eclipse and I defended a licentiate degree. It was cloudy in Stockholm, so the eclipse was a disappointment, but my defense wasn't and I successfully defended.

I've tried to make the thesis introduction easy to understand and you can now read it here on my blog.

What is the thesis about?

Computer Science is no more about computers than astronomy is about telescopes. – (probably) Edsger Wybe Dijkstra
When Santa Claus needs to find a route around the Earth to distribute all the gifts to children in the shortest possible time, it might take millions of years to compute even if he used all the supercomputers that are currently on Earth. This is an example of a problem in computer science that is not known to be solvable fast even after decades of research.

Maybe we have just not been intelligent enough to find the right approach for this problem. However, if you ask a complexity theorist, they would most likely tell you that it will never be possible. Right now we are not completely sure about this fact, but the evidence is piling up (see the excellent essay The Scientific Case for P≠NP by Scott Aaronson).

If it really is impossible for Santa Claus to find the shortest route to distribute all gifts, what other options does he have? Instead of insisting on finding the shortest route, he might try to find a route that is at most 50% longer than the shortest one. Arguably, this should be an easier task and traveling a 50% longer route could still allow him to distribute all presents in time.

First Attempt

The problem that Santa Claus needs to solve is called the Traveling Salesman Problem (TSP). The famous algorithm by Christophides [Chr76] finds a solution to TSP within an error of 50% from the optimal solution. This is an example of an approximation algorithm, since it does not solve a problem optimally but only approximately, that is within a certain error from the optimal solution.

The time complexity of this algorithm is n2.373 operations [MS04] where n is the number of stops that Santa makes. So a computer running the algorithm makes at most about n2.373 operations.

To get the value of n we need to estimate the number of families with children. According to Gap Minder [Gap11], there are about 1.9 billion children on Earth. The average number of children per family has been estimated to be almost three [Fam06], so we can estimate that Santa Claus will need to make at most 650 million stops. Not all children expect to be visited by Santa Claus but a large fraction does, so this estimate is good enough for our purposes.

If Santa Claus had access to the fastest supercomputer Tianhe-2 (as of November 2014) with the speed of 33.86-petaflops, which is about 3 ⋅ 1016 operations per second, it should take a couple of minutes or hours to finish the computation. We note that the theoretically optimal subroutine taking about n2.373 [MS04] operations might in this case be slower than a subroutine that uses Edmond’s algorithm [Edm65] that needs at most n2.5 operations. In any case, such an algorithm will finish its execution in a couple of days.

A possible problem is the high memory consumption of these algorithms, but for the sake of simplicity of this text let us ignore this problem. A bigger problem might be the 50% error, because a tour that is 50% longer than the shortest one might be too long to distribute all the presents in time.

Improving the Error

The celebrated algorithm by Arora and Mitchell [Aro98, Mit99] can find a solution to TSP within an error of say 20, 10 or 5% from the optimal solution. We can pick any error margin we like, but the smaller the error the longer the running time will be. The algorithm works provided that the problem is situated in a Euclidean space. For the purpose of this text, we only need to know that the well-known 2-dimensional (2D) plane or 3-dimensional (3D) space are both Euclidean.

We could pretend that the Earth is flat by using one of the many map projections. Unfortunately, map projections do not preserve an important geometric property, namely that the space is Euclidean and thus cannot be used by the algorithm.

Let us then try using 3 dimensions. The Arora-Mitchell algorithm assumes that the shortest path between two points is the straight line connecting them, but this is a problem for Santa, since he cannot travel under the ground. As it turns out, it is not such a big problem in the end.

Santa Claus can run the Arora-Mitchell algorithm on all positions of children on Earth as if they were simple points in a 3-dimensional space. Then he follows the route returned by the algorithm with the important change that he flies over the Earth’s surface instead of following the straight line under ground. How much longer is the route when flying over the Earth’s surface?

The most remote inhabited place on Earth, Tristan da Cunha, is about 2000 kilometers from the nearest inhabited land. However, the direct distance through the Earth is about 11.5 kilometers shorter, which is only about 0.5% smaller. The situation is shown on the picture below.

The distance between Tristan da Cunha and the nearest inhabited place Saint Helen is about 2000 kilometers. The direct distance through the Earth is about 11.5 kilometers shorter, which is only about 0.5% smaller.
Of course we cannot be sure that 2000 kilometers will be the longest distance between two stops found by the algorithm, however it will most likely not happen very often in the optimal tour. Human settlements are fairly spread out over the Earth’s surface and intuitively an optimal tour should not make a lot of long jumps—it is likely more efficient to first distribute all gifts in Asia and then go to Europe rather than flying 2000 kilometers back and forth all the time.

We thus have a strong reason to be optimistic, so let us hope that the Arora-Mitchell algorithm returns a tour such that Santa travels only about 0.5% longer route compared the one following straight lines under ground. The Arora-Mitchell algorithm is able to return a solution within x% of the optimal tour for any error x we choose. How big should x be if we want to get a 10% error?

If your answer is 9.5%, you are close but not completely right. We want to have 1.005 ⋅ (1 + x) = 1.1, so x ≈ 9.45%. Let us now estimate how long the algorithm will run. The number of operations performed by the algorithm in 3 dimensions is at least
where n is the number of families to visit and a is a number that is at least 9 [RS98]. We note that the exact value of a is higher than 9, but for our purposes this information is enough.

Even if Santa Claus had access to the fastest supercomputer Tianhe-2, it would take about 101250 years to run the algorithm (101250 is a number with 1250 zeros at the end). Or equivalently about 101240 times the age of the universe. Even if each person on Earth had such supercomputer and we ran the algorithm in parallel on all the supercomputers, the running time would still be 101230 times the age of the universe.

For comparison, the Held-Karp algorithm [HK62] that makes about n22n operations is the fastest known exact algorithm that finds the optimal route. It would run 10100000000 times the age of the universe. The running time of the Arora-Mitchell algorithm is tiny compared to this one.

Heuristics

Even though the problem that Santa Claus faces may sound artificial, it appears in real life for companies that distribute goods. Instead of approximation algorithms, they often use heuristics, which are computer programs that try to solve a problem but only weak guarantees are known about the quality of their output.

For an approximation algorithm, we always have a guarantee that the output will be of a certain quality, but we might have to pay for this guarantee with slower running time, as in the case of the Arora-Mitchell algorithm. Heuristics, on the other hand, are usually very fast but we might be unlucky and receive a solution that is not good enough.

In 1947, Dantzig [Dan51] developed the simplex method that became one of the most important algorithms of the 20th century. It performs very fast in practice but for many years its theoretical speed was unknown. In 1970, Klee and Minty [KM72] found some examples where the algorithm became very slow. The algorithm continued to be used in practice and still is until today. It used to have a similar status as heuristics, since we did not know when and why it performs well.

In 1977, Borgwardt [Bor86] found a class of linear programs that are provably solved quickly by the simplex method. Subsequently, other people have found cases where the simplex method performs well. Finally, in 2001—five decades after the algorithm was discovered—Spielman and Teng developed a powerful tool called smoothed analysis [ST04] that explained why the simplex method works fast in practice while there are rare cases where it is very slow.

For many real-world problems, heuristics are both faster and better performing than approximation algorithms and we do not know why, as used to be the case for the simplex method. It is not unheard of that heuristics achieve 1% error as well as they are very fast, while the best-known approximation algorithm only achieves an error in the order of tens of percents (see for example [JM07]). Some people use this fact to argue against the use of complexity theory, but we would argue the exact opposite. Since some heuristics seem to perform well, we should study them more and try to figure out why they perform so well or find cases where they do not, as we did in the case of the simplex method. If anything, this is an argument for more research in complexity theory, not less.

What Should Complexity Theorists do?

There are several interesting research directions that help us. For example, we can try to find faster approximation algorithms for which we do not have to wait 101250 years to finish. We can also try to prove that some heuristics used in practice perform very well, hence turning a heuristic into an approximation algorithm. The hardest alternative of all is to prove that there will never be an algorithm that finds good solutions and is fast at the same time. Such negative results are called hardness results, because they prove that a problem is hard to solve fast.

History has shown that it is important to be both optimistic and skeptical at the same time. Some problems were thought to be hard but an algorithm was found in the end; while for other problems, a very simple and naive algorithm turned out to be the best we can hope for. However, for most of the problems, their complexity is still not well established. The best-known algorithms are often very far from the best-known hardness results and the truth can lie anywhere in between.

What is the Contribution of this Thesis?

In the past decades, linear programming (LP) has been successfully used to develop approximation algorithms for various optimization problems. The simplex method mentioned earlier is used to solve linear programs and is considered to be one of the most important algorithms of the twentieth century, which underlines the importance of linear programming in computer science.

The so-called assignment LP lead to substantial progress for various allocation problems, where items are allocated to players or machines. An example of such problem is scheduling unrelated parallel machines, where computer tasks are to be scheduled on a number of machines such that the last one is finished as soon as possible. Unfortunately, we know that the best-known approximation algorithms for this problem already have the best approximation ratio that any algorithm using the assignment LP can achieve. The bound on the achievable approximation ratio by an LP is called the integrality gap of the LP.

We have thus reached the limits of the assignment LP. The natural question is then whether a different LP formulation can lead to better algorithms. We answer this question positively for variants of two allocation problems: max-min fair allocation and maximum budgeted allocation, which we define in later chapters. This is achieved by using a more powerful LP formulation called the configuration LP that has exponential size. Exponential size is considered inefficient, but configuration LP can be approximated efficiently. This is where the title of the thesis comes from, since we use exponential linear programs in an efficient way.

The restricted max-min fair allocation, also known as the restricted Santa Claus problem, is one of few problems that has a better polynomial estimation algorithm than approximation algorithm. An estimation algorithm estimates the value of the optimal solution, but is not necessarily able to find the optimal solution. The configuration LP can be used to estimate the optimal value within a factor of 1/(4 + ε) for any ε > 0, but it is not known how to efficiently find a solution achieving this value. We give an approximation algorithm with the same approximation guarantee but improve the running time to nO(log n). Our techniques also have the interesting property that although we use the rather complex configuration LP in the analysis, we never actually solve it and therefore the resulting algorithm is purely combinatorial.

For the maximum budgeted allocation (MBA) we prove that the integrality gap of the configuration LP is strictly better than 3/4 and provide corresponding polynomial time rounding algorithms for two variants of the problem: the restricted MBA and the graph MBA. Finally, we improve the best-known upper bound on the integrality gap for the general case from 5/6 ≈ 0.833 to 2√2 − 2 ≈ 0.828 and also show hardness of approximation results for both variants studied.

Further reading

The full thesis is available for download and you can also have a look at my slides, which contain plenty of additional pictures.

Bibliography


[Aro98]    Sanjeev Arora. Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems. J. ACM, 45(5):753–782, 1998.
[Bor86]    Karl Heinz Borgwardt. A Probabilistic Analysis of the Simplex Method. Springer-Verlag New York, Inc., New York, NY, USA, 1986.
[Chr76]    Nicos Christofides. Worst-case analysis of a new heuristic for the traveling salesman problem. Technical report, CMU, 1976.
[Dan51]    George B Dantzig. Maximization of a linear function of variables subject to linear inequalities, in activity analysis of production and allocation. 1951.
[Edm65]    Jack Edmonds. Paths, trees, and flowers. Canadian Journal of mathematics, 17(3):449–467, 1965.
[Fam06]    Number of people in a family. http://web.archive.org/web/20140819085940/http://hypertextbook.com/facts/2006/StaceyJohnson.shtml, 2006. Accessed: 2014-08-19.
[Gap11]    The world has reached peak number of children! http://web.archive.org/web/20141120230405/http://www.gapminder.org/news/world-_peak-_number-_of-_children-_is-_now/, 2011. Accessed: 2014-11-20.
[HK62]    Michael Held and Richard M Karp. A dynamic programming approach to sequencing problems. Journal of the Society for Industrial & Applied Mathematics, 10(1):196–210, 1962.
[JM07]    David S Johnson and Lyle A McGeoch. Experimental analysis of heuristics for the stsp. In The traveling salesman problem and its variations, pages 369–443. Springer, 2007.
[KM72]    Victor Klee and George J Minty. How good is the simplex algorithm? 1972.
[KMN+14]   Christos Kalaitzis, Aleksander Madry, Alantha Newman, Lukas Polacek, and Ola Svensson. On the configuration lp for maximum budgeted allocation. In IPCO, pages 333–344, 2014.
[Mit99]    Joseph S. B. Mitchell. Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric tsp, k-mst, and related problems. SIAM J. Comput., 28(4):1298–1309, 1999.
[MS04]    M. Mucha and P. Sankowski. Maximum matchings via gaussian elimination. In Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on, pages 248–255, Oct 2004.
[PS12]    Lukas Polacek and Ola Svensson. Quasi-polynomial local search for restricted max-min fair allocation. In ICALP, pages 726–737, 2012.
[RS98]    Satish B Rao and Warren D Smith. Approximating geometrical graphs via “spanners” and “banyans”. In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pages 540–550. ACM, 1998.
[ST04]    Daniel A. Spielman and Shang-Hua Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. J. ACM, 51(3):385–463, 2004.

13 April 2015

High-fat diet in the Arctic

Arctic explorers carry a couple of kilograms of butter, because it contains many calories per gram. Some of them eat a stick of butter for breakfast as well as dinner. Me and Martin also bet on fat when we went to Kebnekaise: we brought butter, goose fat, coconut oil, sausages, bacon, frozen meatballs and almonds. I counted at least 3 kilograms of fat but we probably had more. You have to do this if you want to be considered cool in the Arctic circles.

Kebnekaise is a mountain area located beyond the Arctic Circle and Kebnekaise is also the name of the highest mountain in Sweden. I have been there two years ago and wanted to come back as soon as possible, despite the horrible weather we have experienced. There is something about the Kebnekaise area that draws me there and it's hard to explain.

Sunday

After arriving to Kebnekaise fjällstation, we went for a short ski ride just above the hut. The snow was horrible, as is normal for the very windy Láddjuvággi valley. It was then easy to convince Martin to go to Tarfala valley in search for better snow. It turned out to be the right call.

Monday

In the morning we went up to Tarfala mountain hut in sunny weather.

Tarfala valley, Storglaciär and Isfallsglaciär
Martin took a nap in the afternoon, so I went alone for a ski ride just above the hut. The snow was much better than yesterday but still very tricky. Thanks to a lot of wind, icy parts mixed with deep pockets of powder. I fell because of this in the bottom flat part and later learned that the whole hut watched me fall through the window. I'm always happy to provide entertainment.

After dinner, the whole hut gathered again at the windows to watch a group of guys skiing with headlamps. I told Martin: "They are either complete idiots or professionals".

There is no water or electricity in the hut and you have to fetch water and wood from the outside in −15 degrees Celsius. After the arrival of the group with headlamps, the hut was packed to the last bed and had the right Arctic atmosphere. The fat in our stomachs also only amplified it.

The Moon and a hairy mountain. My best guess is that wind is blowing snow over the mountain and creating an illusion of hair.

Tuesday

Two years ago me and Kolo unsuccessfully tried to climb Kaskasatjåkka (2076 m), the 4th highest mountain in Sweden. We turned around because of high winds. Me and Martin made a second attempt and the weather was much better this time with clear blue sky. However, it was very windy and cold, so we had to cover our faces regularly to avoid frostbites. We were rewarded with a view that is even better than from Kebnekaise sydtopp, the highest mountain in Sweden.

Western panorama includes 3 of the top 5 highest mountains in Sweden: Kebnekaise sydtopp, Kebnekaise nordtopp and Kaskasapakte. And it's taken from the 4th highest mountain, Kaskasatjåkka.

Wednesday

We woke up to a typical Tarfala weather: very low visibility, snow and strong wind. No wonder this is the most windy place in Sweden.



Luckily for us, the wind was blowing into our backs and it was actually making moving easier. We wanted to go back to the Kebnekaise fjällstation, but also check out the glacier cave inside Pallins halvjökel.

You can make a couple of ski turns in the glacier cave

The glacier cave provided a nice shelter, but we had to leave it and enter the white world.

Man on the Moon

We arrived at Kebnekaise fjällstation just before noon and then didn't do anything for the rest of the day.

Thursday

Two years ago I have been ogling Tuolpagorni a lot but we didn't have time to ski it, so I made it my main goal of this vacation.

Tuolpagorni has a bowl on the top, a very unusual formation

The conditions looked awesome: clear blue sky, no wind and a lot of powder snow. Our only worry were avalanches, but a snow pit only showed a dangerous layer more than a meter deep.

It felt very strange to be in Tuolpagorni's flat bowl up in the air. We went up to a saddle below the top, enjoyed the view and then skied down the obvious path.

Our downhill route

It was our first time skiing such a narrow and steep couloir (38 to 40 degreees), but in the end it was easier than expected. The deep snow was very forgiving and the couloir wider than it looks at first.

Our piece of work in the couloir

Wow, what a day! No wind is a once-in-a-lifetime experience in this area and skiing Tuolpagorni is also something we won't forget. Watch Martin's video summarizing the whole day.

Friday

I woke up feeling bad, so I stayed in the hut while Martin went for a short ride near Jökelbäcken. It was time to leave Kebnekaise and head home. I'm sure we'll be back soon.

As usual, a small selection of my photos is on Flickr and a full album from multiple cameras is on Google Photos. Martin also made a video from the whole trip.