Result: Economy of Scale in Algorithm Design ; Économies d'échelle en conception d'algorithmes ; Economy of Scale in Algorithm Design: Approximation Algorithms for Submodular Optimization and Network Design ; Économies d'échelle en conception d'algorithmes: Algorithmes d'approximation pour l'optimisation sous-modulaire et la conception de réseaux

The economy of scale principle, where the cost per unit decreases as the scale of operation increases, is a foundational concept in economics. It naturally arises in diverse real-world systems, from logistics and infrastructure planning to data summarization and information propagation. In such systems, grouping resources, demands, or actions often leads to more efficient outcomes. This behavior is reflected in mathematical models through properties such as submodularity, which captures diminishing returns on the value side, and subadditive capacity cost functions, which formalize buy-at-bulk effects on the cost side.In submodular optimization problems, the economy of scale appears as diminishing marginal gains: each additional element contributes less marginal gain as the solution grows.This framework captures key phenomena, including information redundancy and influence propagation.In the buy-at-bulk facility location problem, the economy of scale manifests on the cost side: satisfying a larger demand becomes cheaper per unit due to amortized setup costs.By leveraging this shared structure, this thesis explores the design of approximation and streaming algorithms for these two classes of problems that capture the principle of economy of scale. We develop algorithmic techniques with provable performance guarantees for problems with complex constraints, across different computational models. These results contribute to the broader understanding of scalable algorithms for decision making tasks where gains or costs exhibit diminishing return structures. ; Cette thèse porte sur la conception d’algorithmes d’approximation pour deux classes majeures de problèmes d’optimisation combinatoire : la maximisation sous-modulaire, ainsi que le problème d’implantation (facility location) couplé à des contraintes de conception de réseau. Ces problèmes, présents dans divers domaines tels que les enchères combinatoires, la maximisation d’influence, la logistique et la planification d’infrastructures, sont généralement ...