:7 November 2016
Sublinear time algorithms. Even as recently as early 2000's, we would be happy to settle for a polynomial time algorithm for any non trivial algorithmic problem. It would had been hard to imagine doing better than linear time; after all, we expect algorithms to consider all of its input in order to make a decision. How the times have changed! For the kinds of data sets that I have been dealing with these days, linear is not good enough. The prevalence of extremely large data sets in a wide variety of settings is growing rapidly and beating linear time has become a matter of practical concern as opposed to mere academic curiosity. One solution often touted to this problem is the MapReduce programming model - processing data sets with parallel, distributed algorithms on large clusters. Although this works well in some cases, it's utility has been blown out of proportion in my humble opinion. In many cases, this paradigm is not applicable or does not yield any significant advantage. This is especially true in many big graph data sets.
If linear time is not good enough, it is natural to wonder the existence of sublinear time algorithms for some of these problems. In fact, there has been a lot of recent interest in this direction. Sublinear time is a crazy concept - it allows algorithms to process only a small fraction of the input and yet demands a reasonable solution. There are a handful of problems for which deterministic sublinear time algorithms are known. But in a majority of cases, the algorithm must use randomization and give approximate answers. There is a growing body of work in this area and recent results have shown that there are classical optimization problems whose values can be approximated in sublinear time. Also, property testing has been applied to give sublinear algorithms for a variety of problems. Further, several cool techniques like low rank approximation of matrices have emerged for designing sublinear algorithms. This is all good news! Still, the scope of sublinear algorithms remains minuscule compared to the problems out there with existing solutions considered efficient a decade ago but are no longer acceptable today.
I am grappling with one such graph matching problem presently, namely, maximum weighted matching (MWM) problem. MWM is a classic graph problem for which exact polytime solutions have been known for some time. But for massive graphs this is a non-starter. There is some (relatively) recent work where linear-time approximate algorithms have been worked out for the unweighted case (Drake & Hougardy, 2003; Pettie & Sanders, 2004). I am trying these, but strongly suspect that they may also not fit the bill. Meanwhile, I don't think there are any known sublinear time solutions for this problem. Hope theoreticians are listening!
- Drake, D. E., & Hougardy, S. (2003). Improved linear time approximation algorithms for weighted matchings. In Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques (pp. 14-23). Springer Berlin Heidelberg.
- Pettie, S., & Sanders, P. (2004). A simpler linear time 2/3− ε approximation for maximum weight matching. Information Processing Letters, 91(6), 271-276.