Submodular interval stabbing problem

Abstract

This thesis investigates the Submodular Interval Stabbing Problem (SISP), a generalized optimization framework where jobs associated with temporal intervals must be served within their respective windows to minimize a total cost governed by a submodular function. This model effectively captures the ”diminishing returns” or economies of scale inherent in batch processing, data aggregation, and consolidated service operations. We provide a comprehensive mathematical analysis of SISP, spanning computational complexity, optimal algorithms for restricted cases, and approximation strategies for hi- erarchical structures. We establish that SISP is APX-hard, even when restricted to a strict 2-level laminar structure with monotone submodular functions. Through an approximation-preserving reduction from the Minimum Vertex Cover problem on cubic graphs, we prove that the optimal cost is exactly 2|E|+ OPTVC. For concave func- tions of cardinality, we develop a dynamic programming algorithm and rigorously prove its optimality with a time complexity of O(n3). We extend our study to the Multi-Level Aggregation Problem (MLAP) . By employing geometric time discretization and reduction to a prize-collecting variant, we present an 8-approximation algorithm for the general version involving both holding and delay costs (MLAP-HD). We analyze the worst-case performance of common greedy strategies, providing non-constant lower bounds for the Ratio-Greedy (Ω(ln n)) and Left-to-Right Swapping (Ω(n)) algorithms. Our results map the boundary between tractability and NP-hardness for submodular aggrega- tion, demonstrating that while the general problem is computationally difficult, structured laminar and hierarchical instances admit robust approximation frameworks.