Online Markov Decoding: Lower Bounds and Near-Optimal Approximation Algorithms - Garg, Vikas; Pichkhadze, Tamar (Advances in Neural Information Processing Systems, 2019)