An influential result by Dor, Halperin, and Zwick (FOCS 1996, SICOMP 2000) implies an algorithm that can compute approximate shortest paths for all vertex pairs in ${{\tilde O}}\left( {{{\text{n}}^{2 + {\text{O}}}}\left( {\frac{1}{{\text{k}}}} \right)} \right)$ time1, ensuring that the output distance is at most twice the actual shortest path, provided the pairs are at least k apart, where k ≥ 2. We present the first improvement on this result in over 25 years. Our algorithm achieves roughly same ${{\tilde O}}\left( {{n^{2 + \frac{1}{k}}}} \right)$ runtime but applies to vertex pairs merely O(log k) apart, where $\log \;{\text{k}} \geq 1$. When k=log n, the running time of our algorithm is ${{\tilde O}}\left( {{{\text{n}}^2}} \right)$ and it works for all pairs at least ${\text{O}}(\log \;\log n)$ apart. Our algorithm is combinatorial, randomized, and returns correct results for all pairs with a high probability.

We present a dual fault-tolerant distance oracle for undirected and unweighted graphs. Given a set F of two edges, as well as a source node s and a destination node t, our oracle returns the length of the shortest path from s to t that avoids F in O(1) time with a high probability. The space complexity of our oracle is Õ(n²) , making it nearly optimal in terms of both space and query time. Prior to our work, Pettie and Duan [SODA 2009] designed a dual fault-tolerant distance oracle that required Õ(n²) space and O(log n) query time. In addition to improving the query time, our oracle is much simpler than the previous approach.

The access lemma (Sleator and Tarjan, JACM 1985) is a property of binary search trees (BSTs) that implies interesting consequences such as static optimality, static finger, and working set property on any access sequence X = (x_1,x_2,… ,x_m). However, there are known corollaries of the dynamic optimality that cannot be derived via the access lemma, such as the dynamic finger, and any o(log n)-competitive ratio to the optimal BST where n is the number of keys. In this paper, we introduce the group access bound that can be defined with respect to a reference group access tree. Group access bounds generalize the access lemma and imply properties that are far stronger than those implied by the classical access lemma. For each of the following results, there is a group access tree whose group access bound 1) Is O(√{log n})-competitive to the optimal BST. 2) Achieves the k-finger bound with an additive term of O(m log k log log n) (randomized) when the reference tree is an almost complete binary tree. 3) Satisfies the unified bound with an additive term of O(m log log n). 4) Matches the unified bound with a time window k with an additive term of O(m log k log log n) (randomized). Furthermore, we prove the simulation theorem: For every group access tree, there is an online BST algorithm that is O(1)-competitive with its group access bound. In particular, any new group access bound will automatically imply a new BST algorithm achieving the same bound. Thereby, we obtain an improved k-finger bound (reference tree is an almost complete binary tree), an improved unified bound with a time window k, and matching the best-known bound for Unified bound in the BST model. Since any dynamically optimal BST must achieve the group access bounds, we believe our results provide a new direction towards proving o(log n)-competitiveness of the Splay tree and Greedy, two prime candidates for the dynamic optimality conjecture.

We present an f-fault tolerant distance oracle for an undirected weighted graph where each edge has an integral weight from [1 … W]. Given a set F of f edges, as well as a source node s and a destination node t, our oracle returns the shortest path from s to t avoiding F in O((cf log(nW))O(f2)) time, where c > 1 is a constant. The space complexity of our oracle is O(f4n2log2 (nW)). For a constant f, our oracle is nearly optimal both in terms of space and time (barring some logarithmic factor).

Greedy BST (or simply Greedy) is an online self-adjusting binary search tree defined in the geometric view ([Lucas, 1988; Munro, 2000; Demaine, Harmon, Iacono, Kane, Patrascu, SODA 2009). Along with Splay trees (Sleator, Tarjan 1985), Greedy is considered the most promising candidate for being dynamically optimal, i.e., starting with any initial tree, their access costs on any sequence is conjectured to be within O(1) factor of the offline optimal. However, despite having received a lot of attention in the past four decades, the question has remained elusive even for highly restricted input. In this paper, we prove new bounds on the cost of Greedy in the “pattern avoidance” regime. Our new results include: • The (preorder) traversal conjecture for Greedy holds up to a factor of O(2α(n)), improving upon the bound of 2α(n)O(1) in (Chalermsook et al., FOCS 2015) where α(n) is the inverse Ackermann function of n. This is the best known bound obtained by any online BSTs. • We settle the postorder traversal conjecture for Greedy. Previously this was shown for Splay trees only in certain special cases (Levy and Tarjan, WADS 2019). • The deque conjecture for Greedy holds up to a factor of O(α(n)), improving upon the bound 2O(α(n)) in (Chalermsook, et al., WADS 2015). This is arguably “one step away” from the bound O(α*(n)) for Splay trees (Pettie, SODA 2010). • The split conjecture holds for Greedy up to a factor of O(2α(n)). Previously the factor of O(α(n)) was shown for Splay trees only in a special case (Lucas, 1988). The input sequences in traversal and deque conjectures are perhaps “easiest” in the pattern-avoiding input classes and yet among the most notorious special cases of the dynamic optimality conjecture. Key to all these results is to partition (based on the input structures) the execution log of Greedy into several simpler-to-analyze subsets for which classical forbidden submatrix bounds can be leveraged. We believe that this simple method will find further applications in doing amortized analysis of data structures via extremal combinatorics. Finally, we show the applicability of this technique to handle a class of increasingly complex pattern-avoiding input sequences, called k-increasing sequences. As a bonus, we discover a new class of permutation matrices whose extremal bounds are polynomially bounded. This gives a partial progress on an open question by Jacob Fox (2013). * The full version of the paper can be accessed at https://arxiv.org/abs/2211.04112

In a graph G with a source s, we design a distance oracle that can answer the following query: Query(s,t,e) - find the length of shortest path from a fixed source s to any destination vertex t while avoiding any edge e. We design a deterministic algorithm that builds such an oracle in Õ(m √n) time. Our oracle uses Õ(n √n) space and can answer queries in Õ(1) time. Our oracle is an improvement of the work of Bilò et al. (ESA 2021) in the preprocessing time, which constructs the first deterministic oracle for this problem in Õ(m √n+n²) time. Using our distance oracle, we also solve the single source replacement path problem (Ssrp problem). Chechik and Cohen (SODA 2019) designed a randomized combinatorial algorithm to solve the Ssrp problem. The running time of their algorithm is Õ(m √n + n²). In this paper, we show that the Ssrp problem can be solved in Õ(m √n + |ℛ|) time, where ℛ is the output set of the Ssrp problem in G. Our Ssrp algorithm is optimal (upto polylogarithmic factor) as there is a conditional lower bound of Ω(m √n) for any combinatorial algorithm that solves this problem.

One of the classical line of work in graph algorithms has been the Replacement Path Problem: given a graph G, s and t, find shortest paths from s to t avoiding each edge e on the shortest path from s to t. These paths are called replacement paths in literature. For an undirected and unweighted graph, (Malik, Mittal, and Gupta, Operation Research Letters, 1989) and (Hershberger and Suri, FOCS 2001) designed an algorithm that solves the replacement path problem in Õ (m + n) time1. It is natural to ask whether we can generalize the replacement path problem: can we find all replacement paths from a source s to all vertices in G? This problem is called the Single Source Replacement Path Problem.

Given an undirected unweighted graph G and a source set S of |S| = sigma sources, we want to build a data structure which can process the following query Q(s,t,e): find the shortest distance from s to t avoiding an edge e, where s in S and t in V. When sigma=n, Demetrescu, Thorup, Chowdhury and Ramachandran (SIAM Journal of Computing, 2008) designed an algorithm with O~(n^2) space and O(1) query time. A natural open question is to generalize this result to any number of sources. Recently, Bil{ò} et. al. (STACS 2018) designed a data-structure of size O~(sigma^{1/2}n^{3/2}) with the query time of O(sqrt{n sigma}) for the above problem. We improve their result by designing a data-structure of size O~(sigma^{1/2} n^{3/2}) that can answer queries in O~(1) time. In a related problem of finding fault tolerant subgraph, Parter and Peleg (ESA 2013) showed that if detours of replacement paths ending at a vertex t are disjoint, then the number of such paths is O(sqrt{n sigma}). This eventually gives a bound of O(n sqrt{n sigma}) = O(sigma^{1/2}n^{3/2}) for their problem. Disjointness of detours is a very crucial property used in the above result. We show a similar result for a subset of replacement path which may not be disjoint. This result is the crux of our paper and may be of independent interest.

We present an algorithm for maintaining a maximal matching in a graph under addition and deletion of edges. Our algorithm is randomized and it takes expected amortized $O(\log n)$ time for each edge update, where $n$ is the number of vertices in the graph. Moreover, for any sequence of $t$ edge updates, the total time taken by the algorithm is $O(t\log n + n \log^2 n)$ with high probability. (Original article at https://doi.org/10.1137/130914140.)

Recently there has been extensive work on maintaining (approximate) maximum matchings in dynamic graphs. We consider a generalisation of this problem known as the maximum b-matching: Every node v has a positive integral capacity b_v, and the goal is to maintain an (approximate) maximum-cardinality subset of edges that contains at most b_v edges incident on every node v. The maximum matching problem is a special case of this problem where b_v = 1 for every node v. Bhattacharya, Henzinger and Italiano [ICALP 2015] showed how to maintain a O(1) approximate maximum b-matching in a graph in O(log^3 n) amortised update time. Their approximation ratio was a large (double digit) constant. We significantly improve their result both in terms of approximation ratio as well as update time. Specifically, we design a randomised dynamic algorithm that maintains a (2+epsilon)-approximate maximum $b$-matching in expected amortised O(1/epsilon^4) update time. Thus, for every constant epsilon in (0, 1), we get expected amortised O(1) update time. Our algorithm generalises the framework of Baswana, Gupta, Sen [FOCS 2011] and Solomon [FOCS 2016] for maintaining a maximal matching in a dynamic graph.

Let G=(V,E) be a graph with n vertices and m edges, with a designated set of sigma sources S subseteq V. The fault tolerant subgraph for any graph problem maintains a sparse subgraph H=(V,E') of G with E' subseteq E, such that for any set F of k failures, the solution for the graph problem on G\F is maintained in its subgraph H\F. We address the problem of maintaining a fault tolerant subgraph for computing Breath First Search tree (BFS) of the graph from a single source s in V (referred as k FT-BFS) or multiple sources S subseteq V (referred as k FT-MBFS). We simply refer to them as FT-BFS (or FT-MBFS) for k=1, and dual FT-BFS (or dual FT-MBFS) for k=2. The problem of k FT-BFS was first studied by Parter and Peleg [ESA13]. They designed an algorithm to compute FT-BFS subgraph of size O(n^{3/2}). Further, they showed how their algorithm can be easily extended to FT-MBFS requiring O(sigma^{1/2}n^{3/2}) space. They also presented matching lower bounds for these results. The result was later extended to solve dual FT-BFS by Parter [PODC15] requiring (n^{5/3}) space, again with matching lower bounds. However, their result was limited to only edge failures in undirected graphs and involved very complex analysis. Moreover, their solution doesn't seems to be directly extendible for dual FT-MBFS problem. We present a similar algorithm to solve dual FT-BFS problem with a much simpler analysis. Moreover, our algorithm also works for vertex failures and directed graphs, and can be easily extended to handle dual FT-MBFS problem, matching the lower bound of O(sigma^{1/3}n^{5/3}) space described by Parter [PODC15]. The key difference in our approach is a much simpler classification of path interactions which formed the basis of the analysis by Parter [PODC15].

Nowadays, brick-and-mortar stores are finding it extremely difficult to retain their customers due to the ever increasing competition from the online stores. One of the key reasons for this is the lack of personalized shopping experience offered by the brick-and-mortar stores. This work considers the problem of persona based shopping recommendation for such stores to maximize the value for money of the shoppers. For this problem, it proposes a non-polynomial time-complexity optimal dynamic program and a polynomial time-complexity non-optimal heuristic, for making top-k recommendations by taking into account shopper persona and her time and budget constraints. In our empirical evaluations with a mix of real-world data and simulated data, the performance of the heuristic in terms of the persona based recommendations (quantified by similarity scores and items recommended) closely matched (differed by only 8% each with) that of the dynamic program and at the same time heuristic ran at least twice faster compared to the dynamic program.

We present an algorithm for maintaining maximal matching in a graph under addition and deletion of edges. Our algorithm is randomized and it takes expected amortized $O(\log n)$ time for each edge update, where $n$ is the number of vertices in the graph. While there exists a trivial $O(n)$ time algorithm for each edge update, the previous best known result for this problem is due to Ivković and Lloyd [ Lecture Notes in Comput. Sci. 790, Springer-Verlag, London, 1994, pp. 99--111]. For a graph with $n$ vertices and $m$ edges, they gave an $O( {(n+ m)}^{0.7072})$ update time algorithm which is sublinear only for a sparse graph. For the related problem of maximum matching, Onak and Rubinfeld [ Proceedings of STOC'10, Cambridge, MA, 2010, pp. 457--464] designed a randomized algorithm that achieves expected amortized $O(\log^2 n)$ time for each update for maintaining a $c$-approximate maximum matching for some unspecified large constant $c$. In contrast, we can maintain a factor 2 approximate maximum matching in expected amortized $O(\log n )$ time per update as a direct corollary of the maximal matching scheme. This in turn also implies a 2-approximate vertex cover maintenance scheme that takes expected amortized $O(\log n )$ time per update. (A corrected version is at https://epubs.siam.org/doi/abs/10.1137/16M1106158.)

A sparse subgraph G' of G is called a matching sparsifier if the size or weight of matching in G' is approximately equal to the size or weight of maximum matching in G. Recently, algorithms have been developed to find matching sparsifiers in a static bipartite graph. In this paper, we show that we can find matching sparsifier even in an incremental bipartite graph. This observation leads to following results: 1. We design an algorithm that maintains a (1+epsilon) approximate matching in an incremental bipartite graph in O(log^2(n) / (epsilon^{4}) update time. 2. For weighted graphs, we design an algorithm that maintains (1+epsilon) approximate weighted matching in O((log(n)*log(n*N)) / (epsilon^4) update time where \maxweight is the maximum weight of any edge in the graph.

We present the first data structures that maintain near optimal maximum cardinality and maximum weighted matchings on sparse graphs in sub linear time per update. Our main result is a data structure that maintains a (1+ε) approximation of maximum matching under edge insertions/deletions in worst case Õ(?mε-2) time per update. This improves the 3/2 approximation given by Neiman and Solomon [20] which runs in similar time. The result is based on two ideas. The first is to re-run a static algorithm after a chosen number of updates to ensure approximation guarantees. The second is to judiciously trim the graph to a smaller equivalent one whenever possible. We also study extensions of our approach to the weighted setting, and combine it with known frameworks to obtain arbitrary approximation ratios. For a constant ε and for graphs with edge weights between 1 and N, we design an algorithm that maintains an (1+ε) approximate maximum weighted matching in Õ(?m log N) time per update. The only previous result for maintaining weighted matchings on dynamic graphs has an approximation ratio of 4.9108, and was shown by An and et al. [2], [3].

We present a fully dynamic algorithm for maintaining approximate maximum weight matching in general weighted graphs. The algorithm maintains a matching M whose weight is at least 1/8 M^{*} where M^{*} is the weight of the maximum weight matching. The algorithm achieves an expected amortized O(log n log C) time per edge insertion or deletion, where C is the ratio of the weights of the highest weight edge to the smallest weight edge in the given graph.

We present an algorithm for maintaining maximal matching in a graph under addition and deletion of edges. Our data structure is randomized that takes $O( \log n)$ expected amortized time for each edge update where $n$ is the number of vertices in the graph. While there is a trivial $O(n)$ algorithm for edge update, the previous best known result for this problem was due to Ivkovi\'c and Llyod\cite{llyod}. For a graph with $n$ vertices and $m$ edges, they give an $O( {(n+ m)}^{0.7072})$ update time algorithm which is sub linear only for a sparse graph. %To the best of our knowledge this %is the first polylog update time for maximal matching that implies an % exponential improvement from the previous results. For the related problem of maximum matching, Onak and Rubinfeld \cite{onak} designed a randomized data structure that achieves $O(\log^2 n)$ expected amortized time for each update for maintaining a $c$-approximate maximum matching for some large constant $c$. In contrast, we can maintain a factor two approximate maximum matching in $O(\log n )$ expected amortized time per update as a direct corollary of the maximal matching scheme. This in turn also implies a two approximate vertex cover maintenance scheme that takes $O(\log n )$expected amortized time per update.

We present a framework for computing with input data specified by intervals, representing uncertainty in the values of the input parameters. To compute a solution, the algorithm can query the input parameters that yield more refined estimates in form of sub-intervals and the objective is to minimize the number of queries.The previous approaches address the scenario where every query returns an exact value. Our framework is more general as it can deal with a wider variety of inputs and query responses and we establish interesting relationships between them that have not been investigated previously. Although some of the approaches of the previous restricted models can be adapted to the more general model, we require more sophisticated techniques for the analysis and we also obtain improved algorithms for the previous model. We address selection problems in the generalized model and show that there exist 2-update competitive algorithms that do not depend on the lengths or distribution of the sub-intervals and hold against the worst case adversary. We also obtain similar bounds on the competitive ratio for the MST problem in graphs.