{"id":"arxiv/2606.14995","url":"https://arxiv.org/abs/2606.14995","tags":["cs.DS","math.CO"],"score":0,"title":"Optimality of Random Regular Graphs in Sparse Network Designs","domain":"cs.DS","source":"arxiv","authors":["Weijia Li","Xiaochun Niu","Yehua Wei","Jiaming Xu"],"reviews":0,"subject":"cs.DS","summary":"The problems of designing sparse networks arise frequently in resource allocation and operations research. In production systems, for example, sparse process flexibility designs are used to handle uncertain demand effectively: the goal is to construct the sparsest bipartite graph between supply and demand that still achieves an expected fulfilled demand comparable to that of a fully flexible system. In middle-mile transportation, sparse delivery-route subgraphs that sustain large matchings after random node deletions help reduce delivery costs; here, the goal is to design the sparsest graph…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-06-12","reactions":{}}