Vikas K. Garg, Tamar Pichkhadze: Online Markov Decoding: Lower Bounds and Near-Optimal Approximation Algorithms. NeurIPS 2019: 5681-5691