Challenges in Approximation Algorithms: Insights and Open Problems

Ten Open problems in Approximation Algorithms: Dead problems society Guy Kortsarz 2 13 2021

My field is approximation algorithms What happened to it? It died of natural causes. It was in fashion for more than 25 years since 1992. Today strong papers in approximation will have difficulty in being accepted to FOCS STOC SODA ICALP. But if it is good APPROX will accept it.

Now other fields are popular Streaming Machine Learning Computer Security Quantom Algorithms. Algorithm Game theory (maybe it is over the hill as well) Computational biology.

David P. Williamson With Shmoys: Open problems They give 10 problems some quite hard and open for a long time. Most of these problems I have no idea about and so I will not present them. I will take the very few that I somewhat know and say a word. I will not define the problem (famous).

Coloring a 3-colorable graph with minimum colors SW ask if you can get log n. I saw a paper by Eden Chlamt c As far as I remember it gave a real possibility for O(log n) but maybe in Quasi-Poly time. I will not be surprised if this one is solved.

Scheduling unrelated machines Improving the 2 seems quite hard. The algorithm that gives ratio 2 by LP is rather simple. Due to Lenstra, Shmoys,Tardos 1990. They showed better than 3/2 is not possible. No progress (unless special cases count) for almost 30 years.

Minimum Steiner Forest A primal-dual 2-approximation algorithm (Agrawal, Klein, Ravi 1995; see also GW 1995). This question is breaking the 2. May not be possible. One of the most basic open problems.

Recently a 40 years central open problem was solved. The tree Augmentation problem. Given a spanning tree T(V,E ) in a graph G(V,E) so that every edges has a cost c(e), find a minimum cost edges collection F E-E so that G+F is 2-edge connected. J. Byrka, F. Grandoni and A.J Ameli give a ratio of less than 1.91.

I was amazed by this paper. Super brilliant paper A new idea. Reduce TAP to the Undirected Steiner Tree case. Maybe TAP is related to the minimum Steiner Forest problem? Maybe we have now a chance to get better than 2 for Steiner forest? I have no argument to support that. Just a feeling.

Survivable network design AKA: Steiner Network. Jain gave a somewhat surprising (maybe for me) ratio 2. Is this the best? Can it be done by a combinatorial algorithm? Seems very hard to answer.

And of course we have TSP Can recently a sensation: the 3/2 was broken to 3/2- for some small constant . The asymmetric version has some constant ratio. Somebody told me (I do not know if he would like it if I say his name) that 2 is the right ratio. Anyway getting 2 is a good open problem.

Inapproximability open problems Lower bound of 2 for VC? Normal lower bound for coloring 3- colorable graphs? Can we prove in some way the Unique Game Conjecture? Is there a log n lower bound for Undirected Multicut?

Dead problems society There is a film Dead Poets Society, directed by Peter Weir, a terribly demagogic film. 1989 Nevertheless, the title is a rip off of the name of that film. Why dead? Maybe because I have no clue how to solve them?

Problem 1: Approximating Multicommodity Buy-At-Bulk State of affairs: O(log3n) ratio for polynomial demands Due to Kortsarz, Nutov, TCS, 2011. For general demands best known O(log4n) by Chekuri, Hajiaghayi, Kortsarz, Salavatipour. In SICOMP

The best known lower bound (sqrt{log n}) Matthew Andrews: Hardness of Buy-at-Bulk Network Design. FOCS 2004. There is no progress in upper or lower bounds, as far as I know, for a very long time. Please solve it next Friday.

Buy at Bulk with protection See a paper by Chandra Chekuri. For this problem there are many hard open problems. I do not know how to solve them. Maybe solve it between Breakfast to Lunch.

Problem 2: FPT-hardness for Clique Is the Clique problem completely FPT inapproximable under the ETH? Complete FPT inapproximability is known for Set Cover. See paper by Karthik, Laekhanukit, Manurangsi. Known to be true under GAP-ETH. Should be one of the easier problems.

Problem 3: Directed Steiner Tree Best know ratio: O(n ) By Charikar et al. Implies polylog in Quasi-Poly time. Recently the best Qusi- Poly time ratio possible was found: O(log2n/loglog n) by Fabrizio Grandoni, Bundit Laekhanukit, Shi Li.

A conjecture of mine Under the ETH conjecture the Directed Steiner Tree problem admits no polylog ratio in time polynomial in n. A paper of Chekuri and Pal showed that under the ETH, Quasi(P) P. Can you think about it a few days and solve it? Thank you.

Problem 4: Shallow Light Trees Shallow light Steiner trees: Given a graph with length 1 on the edges and arbitrary positive costs c(e) on the edges, a root r, and a height bound h. And a collection of terminals. Question: Find a Steiner tree of height at most h and among them minimum cost (the height bound is hard const )

The ratio A ratio similar to the one of Directed Steiner Tree can be derived. Kortsarz, Peleg Known since 1997. In fact if you can not have height even h+1, as hard as DST (easy but not published result). My open question: is there bicriteria (O(1), polylog n) approximation?

How hard is this question? I at least hope it is easier than polylog for DST. But no advance for 22 years. Can you please solve this one in your spare time? Thanks.

Problem 5: The minimum Poise spanning Tree problem Given a Spanning Tree T, let be the largest degree and let D be its diameter. The problem: find a Spanning tree with minimum +D Best known ratio O(log n/log log n) Elkin, Kortsarz 2003.

I have a conjecture I think this problem has a constant ratio. I will be more specific: the best ratio is 3, I think. It s a bit long to say why I think so. Any constant ratio will be impressive. Maybe solve if over the weekend?

Problem 6: The directed Multicut problem Maybe the most difficult problem I ever worked on. The best ratio is O(sqrt{n}) by Gupta. I think that the paper by Charikar et al that claimed better than O(sqrt{n}) is not correct. Its time for an erratum. Costs 1 on edges may be easier.

What is known O(opt) ratio. Anupam Gupta. A paper of mine gives a O(n2/3/opt1/3) ratio for unit costs. Nobody knows it. This means that if opt (sqrt{n}) we can break the sqrt{n}. So assume opt= (sqrt{n}), and improve the ratio. I will be happy if anyone gives better than O(sqrt{n})

Open problem 7: Directed Steiner Forest. A directed graph G(V,E) and costs over the edges, and a collection of pairs {s(i),t(i)}. The goal is to find a subgraph of minimum cost so that for every i, there is a directed path from s(i) to t(i). This is the only problem but Directed Steiner Tree that has o(n) ratio.

What is known The first ratio was n4/5 By Feldman, K, and Nutov. Later I had a SODA paper with Bundit, Eden an Mike. We improved the ratio for the unweighted case to n3/5 I think today n3/5 is known also for the weighted case. I do not follow this problem.

I would tell you to solve in on Friday but The hardness is that the paper is Labelcover hard. Which means that we do not have even a polynomial lower bound. This may not change for a long time. But maybe we can get a sqrt{n} ratio?

Problem 8: Min cost vertex k- connected subgraph problem The best ratio if k=n-o(n) is O(log2n) by Zeev Nutov. For all other values O(log n) is possible. We are failing to give a (log n) lower bound after years of trying. Why? I think the usual reason. I am just not smart enough. You are.

Problem 9: Many problems on Group Steiner Is O(log2n/loglog n) possible in poly time on trees? The integrality gap can not be more than that. Many tried this one, some smart people, and failed. Is there a ratio for general graph that equals the ratio for trees? Do we need FRT to solve the general case?

More open problems Can we give a polylog ratio when the costs are on vertices? Is there a polylog ratio for general graphs if the vertices have degree bounds? The issue with degree bound is that they exclude the use of FRT. For the latter there is polylog in quasi- poly time.

Problem 10: The Dense k- Subgraph In 1993, Kortsarz and Peleg gave O(n2/5) ratio. In 2001 Feige Kortsarz and Peleg gave an O(n{1/3- }) ratio. is very close to 1/60 (very very slightly above that). The best known is roughly O(n1/4) by Charikar et al. Brilliant paper.

The question is Is there any hardness under P NP? So far we know lower bound under the ETH and under random assumptions. I am certain that the ratio by Charikar et al is the best. This is related to the so called Log Density Conjecture . Maybe solve it next Monday?

Are my ten open problems any good? I think they are. Approximation Algorithms reached a dead end. The important problems left are very hard. I advise that students will not go for a Ph. D in Approximation Algorithms.

What to do Maybe do not do a Ph. D. and go to the industry? Theory is a small field. Few come to theory conferences. The field does not have a lot of grant money. Just do not go to theory (either applied fields or the industry).

How did I work on it? I never gave up Approximation Algorithms That being said, I have papers also on On-Line algorithms, Fixed Parameter Tractability, Mechanism Design, exact solutions, Matroids. I have theorems in pure graph theory.

Theoretical Computer Science should change The time in which people like me are doing papers in theoretical computer science has to end. Theoterical computer science should becomes like math Only true geniuses should work on it, and in general not many should work on it.

My first paper was in 1992 In 2022 it will be 30 years from my first paper I was sick for 8 of these years so I actually worked 23 years. It is very tempting to leave research at that time. I do not have the same energy.

I have enough papers More than that, the quality of the best papers counts. Not the quantity I now have 90 Journal papers (if I send everything I have now and its accepted). Five papers some of them good were not sent to journal. So 95 papers as of today. Will I reach 100? I do not know.

October 2022 I will have 7 years to retirement I am not sure I should continue with research by then. My energy went down. And I do not want to just make weak paper for the sake of making papers. Sounds like a good time to retire from research. I have heavy teaching load. But will need to find more things to do.

Why did I present 10 open problems? Because I want every person from theory to write her 10 dead problems society. Why not do it? I know that the 10 chosen ones will be hard. But I feel people in theory should write such a file. Everybody in theory should have such a powerpoint

Please do so. Its fun! I will be happy to hear your 10 favorite open problems. If it is in theory I am likely to understand Do not write on the famous open problems. Just those you worked a lot on. Looking forward to you Dead Problems Society!