Faster Discrete Convex Function Minimization with Predictions: The M-Convex Case

Recent research on algorithms with predictions [29] has demonstrated that we can improve algorithms' performance beyond the limitations of the worst-case analysis using predictions learned from past data. In particular, a surge of interest has been given to research on using predictions to improve the time complexity of algorithms, which we refer to as warm-starts with predictions for convenience. Since Dinitz et al. [11]'s seminal work on speeding up the Hungarian method for weighted bipartite matching with predictions, researchers have extended this idea to algorithms for various problems [7, 35, 10]. Sakaue and Oki [39] have found similarities between the idea and standard warm-starts in continuous convex optimization and extended it to L-convex function minimization, a broad class of discrete optimization problems studied in discrete convex analysis [31]. They thus have shown that warm-starts with predictions can improve the time complexity of algorithms for various discrete optimization problems, including weighted bipartite matching and weighted matroid intersection. In this paper, we extend the idea of warm-starts with predictions to a new direction called M-convex function minimization, another important problem class studied in discrete convex analysis. The M-convexity is in conjugate relation to the L-convexity. Therefore, exploring the applicability of warm-starts with predictions to M-convex function minimization is crucial to broaden further the range of algorithms that can benefit from predictions, as is also mentioned in [39]. Specifically, we focus on an important subclass of M-convex function minimization called laminar convex minimization (Laminar), which forms a large problem class and is widely studied in the field of operations research.