DIMACS
DIMACS REU 2019

General Information

me
Student: Shyamal Patel
Office: CoRE 446
School: Georgia Tech
E-mail: shyamalpatelb@gmail.com
Project: Provable Graph Algorithms

Project Description

We are often faced with problems in which we are not given all the information up front but rather in pieces. In such cases online algorithms are a must. However being forced to stick to past decisions can often be very restrictive. For instance, if we want to maintain a large matching in a bipartite graph we can do no better than \( (1-1/e) \) OPT. Even worse, if we want to schedule unit weight tasks on machines we can do no better than a \( O(\log(n)) \) approximation. As such, it is natural to allow ourselves to make a few changes throughout the process so we can surmount these lower bounds. Ideally, we would like to be able to maintain a good solution without making too many changes, since allowing ourselves to make an unlimited number of change trivializes the problem. In this domain of online algorithms with recourse, a number of positive results have shown that we can in fact make few changes and get a good solution. Specifically, it is know that only \( O(n) \) changes are needed to maintain an \( O(1) \) approximate load balancing solution with \( n \) tasks in the unit weight case and \( O(n \log^2(n)) \) changes are needed for \(n\) insertions to maintain a maximum cardinality matching online. In this project, we will be attempting to extend these results into the weighted setting. Specifically, we will work to maintain weighted matchings, approximate weighted matchings, and approximations to the scheduling problem on unrelated machines.

Weekly Log

Week 1:
This week was largely getting acquainted with the problems and reading about previous results. I looked at "Online Bipartite Matchings with Amortized \(O(log^2(n))\) replacements" by Bernstein, Holm, and Rotenberg, "Fully Dynamic \((1+\epsilon)\)-Approximate Matchings" by Gupta and Peng, and "Maintaining Assignments Online: Matching, Scheduling, and Flows" by Gupta, Kumar, and Stein. I also got a chance to meet with Dr. Bernstein to discuss the problems we'd be considering which are primarily weighted versions of the problems considered in his paper and that of Gupta et al. I was able find some lower bounds for the case of maintaining an maximum weight perfect matching. I also showed a variant of Hall's Theorem that holds in the case of scheduling with vertex weights; however, I am unsure how to use this currently.
Week 2:

This week we gave our presentations on our problems. The presentation went well over all and it was nice to learn more about the other students projects. In terms of progress on my own problem, I primarily made a few more simply observations: I was able to make a few modifications to my counter example to say something in the case in which the maximum weight matching has smaller total weight. This lower bound coupled with a trivial upperbound I found this week for maintaining an approximate maximum weight matchineg shows that we can do strictly better if we only want a \((1 + \epsilon)\) approximation. I was somewhat interested in showing a lower bound that we needed \(\omega(n)\) changes even in the approximate case. I was hoping that some sort of a fractional relaxation would make the problem more tractable; however, even in the fractional case I didn't see a good way to proceed. (A positive result for the fractional case may have also been helpful in getting some sort of a positive result using an idea like that of Gupta et al. in section 8 of their paper.) I was also able to show that any vertex that was unmatched at some time, can be assumed to stay unmatched for the remainder of the algorithm. The proof was more involved that I would have expected; I think there should be a much simpler way to show this.

Meanwhile, The hunt for a positive result in the case of a maximum weighted matching continues. I am currently not completely conviced that there isn't an example with bounded edge weights (even weights of just 1 and 2) that requires \(\Omega(n^2)\) changes. I haven't met with much success so far in finding a lowerbound or this case or showing an upperbound. I do hope that we can do this without making many changes. In order to show this, I spent some time looking into primal dual algorithms after reading an interesting interpretation of the method to reduce weighted problems to a collection of unweighted ones. Very recently, I stumbled on "A Decomposition Theorem for Maximum Weight Bipartite Matchings" by Kao, Lam, Sung, and Ting. I think the ideas presented there might be useful to say something about maintiaining a weighted vertex cover (the dual problem of maximum weight matching) online without many changes. Hopefully this will lead to a positive result (at least for the case of bounded weights). The paper also gives an algorithm, which seems more intimately related to the weight of the matching, so that might be useful as well since any positive result in this domain depends on the weight of the matching.

Looking at the LP and primal dual algorithms also should be helpful for the semi-matchings since many of the algorithms in that domain use LP relaxations and rounding. I've collected a few paper that I need to read on these - mainly a \(\log(n)\) online approximation to the problem and a \(2\) approximation offline solution.

Week 3:

I met with my mentor this week. We discussed some of the ideas Aditi and I had and suggested a few problems to direct our attention to mainly: 1) Upper and lower bounds for matchings in the case of vertex weights, 2) An upper bound for generalized weighted matchings with \(\tilde{O}(w_{max} n) \) recourse, 3) An \(O(1)\) approximation to the general weighted edge orientation problem with \(O(1)\) amortized recourse per edge, 4) vertex weighted load balancing with \(O(1)\) recourse per vertex, and 5) edge weighted load balancing with \(O(1)\) recourse per vertex. He also suggested a few ideas for working on problems (2) and (3).

I also had a chance to think about some of my ideas from last week, although I they didn't result in anything promising as of yet. I first notice that maintaining an optimal solution to the dual could require strictly less recource than maintianing a primal solution. This isn't that surprising and the difference I found is only by a log factor (Konig's theorem let's us maintain a vertex cover with O(1) recourse while we need O(log(n)) recourse to maintain a matching.) It would still be interesting if they only ever differed by polylog factors (although this is probably a bit of a long shot). I spend also spent some time thinking about graph unravelling, but ended up coming to the conclusion that it isn't much better than just maintianing weights with the Hungarian algorithm since we can keep them positive that way as well. Along these lines I also simplified my proofs a bit fact that unmatched vertices will remain unmatched. Moreover we can view the problem as an offline question about a variant of the Hungarian algorithm, but this doesn't seeem to make the analysis easier... Professor Bernstein suggested that I try to somehow use the duals as a potential function since they clearly only change \(O(w_{max} N)\) times and the values on the servers are increasing. But I am unsure how to relate this to the recouse of the algorithm.

I also got a chance to look over the approximation algorithm by Tardos et al. I thought it was quite nice, but I have no immediate ideas on how to work with it cleanly in an online fashion. (My current approach is the most straightforward one in which we solve the LP everytime. Hopefully some sort of sensitivity result will then show we don't change too much.

In terms of positive results, Aditi was able to come up with an improved lower bound for the weighted vertex matching problem. I think this should lead to a lower bound of \(\Omega(w_{max} n)\), which matches the upper bound we are looking for. Additionally, I was able to use some of the ideas that Professor Bernstein suggested to answer (3). I think these ideas will generalize to show that we can use amortized \(O(1)\) recourse per vertex to get an \(O(1)\) approximation in the case of bounded degree.

Week 4:
I was able to work out and prove that we could use amortized \(O(1)\) recourse per vertex to get an \(O(1)\) approximation in the case of bounded degree. Also, we verified that Aditi's example actually gave the \(O(w_{max} n) \) bound that we were looking for. I was largely stuck this week, but was inspired by a few ideas thrown around in a meeting this week. Mainly we were largely looking for a solution with \(O(W_{max} n log^2(n)) \) recourse to the weighted vertex maximum matching problem. However, after Aditi presented some of her ideas, it seemed that the algorithm we are looking for may very well use \(O(W_{max} n + nlog^2(n)) \) recourse. This seems very non-intuitive as we essitiall get \( o(\log^2(n)\) (This should probably be a \(n\log(n)\) but that would need a better SAP analysis.) That said after the meeting I was able to bound one of three types of changes with \(O(w_{max} n) \) changes which seem promising. Moreover, one of the other cases should hopefully follow from a closer look and modifications of a paper from Bernstein et al. I also found a nice presentation of this algorithm in terms of looking for the shortest path in the Hungarian algorithm which is nice. The specific bound I found also extends to the case of general edge weights.
Week 5:
I was finally able to prove an upperbound for the edge weighted matching setting, showing that we need \(\tilde{O}(nW_{max})\) changes to maintain an exact weight matching. I spent most of the week going through the details, proving a bunch of lemmas, and writing up the proof. I especially liked the proof as it reduced the weighted setting to the unweighted setting, much like the Hungarian algorithm reduces weighted matchings to unweighted matchings. It would now be nice for this problem to find a lower bound requiring \(\Omega(W_{max}n \log(n))\) changes as this would (assuming the SAP conjecture is true) give matching upper and lower bounds.
Week 6:

I spent some time thinking about getting a good lower bound but haven't really been able to find anything. I think some sort of branching, as Aditi suggested, is likely important to getting such a lower bound. That said I've still been trying to show that the suffixes can result in \(Omega(nW_{max})\) changes, since that would at least give me some comfort in thinking the argument might be tight. (Aditi's example for vertex weights shows the analysis for prefixes is tight).

One interesting note I realized is that I think in the proof I used I could have made a "better" guarantee. In the sense that if there were an algorithm better than SAP, we could simply run the the better algorithm on the carbon copy graph and get smaller recourse. It would be nice if there was a general relationship like that for some class primal dual algorithms (I'd like to think this would be particularly nice since primal dual algos reduce a weighted problem to the unweighted case and such a theorem would say that online recourse wise the same thing happens). Unfortunately currently the proof still uses structure in the analysis of the prefixes. Also, I'd have to familiarize myself with the more general framework of primal dual algorithms to know if this would work.

In terms of load balancing, I still haven't found a good avenue to attack the general problem. I ended up wasting some time thinking that the LP whose solutions could be rounded could be solved by a min cost max flow. (It's clearly not the case since the LP is clearly not even an integral polytope...) The approach I was hoping would work was: Find vertex solutions for approximate min cost max flow. Afterward round these solutions using the scheme in the 2 approximation (I think we'd likely end up not finding a perfect matching but settling for a semi-matching where each server has bounded degree if this idea were to work). Hopefully, there is a nice (combinatorial) way to solve the fractional version of load balancing, and this approach still has some hope. Unfortunately I'm not too certain how easy the analysis would be since I don't even know how to obtain an approximate solution to max weight matching with O(n) recourse. (The natural way to do this I thought might be to adapt the Hungarian algorithm by generalizing the definition of a tight edge but modifying the weights in this setting still eludes me. Moreover the stopping condition cannot be when all the clients are matched since we then face the Omega(nlog(n)) lowerbound for maintaining an exact matching. As an aside, a trivial argument gives us O(nlog(n)) changes anyways so it would really only be interesting if we could get a O(n) recourse solution.)

Over the weekend I was able to show that the greedy algorithm makes at least \(\Omega(n \sqrt{W_{max}})\) changes using my original counter example graph. I believe that it should likely be true that it makes at most \(O(\min(|E|, nW_{max}))\) changes, but since we want a result independent of the max weight and with \(O(n)\) recourse proving this wouldn't be helpful. Professor Bernstein suggested a slight modification to the algorithm that I will consider and will hopefully give an \(O(1)\) approximation with \(O(n)\) recourse.

Week 7:
I spent a decent amount of time working on my final presentaiton this week, which I think went decently. (Although the analogy I tried to give broke down a little bit...) Thankfully, I was also able to get some research done as well. I went through the analysis of the algorithm that Professor Bernstein gave and with some slight modifications was able to prove that it is a \((2+\epsilon)\) approximation that makes at most \(O_\epsilon(n)\) changes in total. I was also able to think about the algorithm that Professor Bernstein gave for the vertex weigthed matchings and prove that it was correct. However, I am still unsure of how to bound the recourse of the algorithm. I also spend some time thinking about whether or not we can maintain an maximum weight maximum cardinality matching with not too many changes. Unfortunately the classical reduction here usually relies on adding a weight of \(nw_{max} \) to all of the edges which makes the bound for maximum weight matchings trivial. Using the same proof technique, however, it suffices be able to maintain a good set of dual weights for the problem without too many changes. For some reason, I feel like manually controlling weight and potentially using a vertex cover to do so might be useful. However, I haven't been able to saying anything non-trivial as of yet.
Week 8:
I spent more time thinking of how to maintain a maximum weight maximum cardinality matching, but I wasn't able to get too far unfortunately. I had hoped that all of the dual weights would be in \([0,w_{max}] \cup [nw_{max}, (n+1)w_{max}]\) but after failing to prove that for a while I was able to find a simple counter example. I also found a simpler proof for the result for maintianing maximum weight matchings. The idea is simply that the duals weights in some sense don't matter in the Hungarian algorithm. It then follows that we can assume that there are no prefixes and only suffixes, which removes the need for a number of the lemmas. That said, having been able to not find an improved counter example with log factors, I think the answer may in fact be \(O(w_{max}n + n\log(n))\). With this in mind, I then believe that the simpler argument won't be able to generalize to prove this statement while there is a non-zero chance the other method can. So, in light of this I may stick with the more complex argument for now. Other than that I spent some time thinking about vertex load balancing but haven't gotten too far on that front.

Presentations