Optimization problems in networks and queues

This dissertation presents a collection of results in applied probability, stochastic processes, and optimization, unified by their mathematical techniques. Each chapter studies a distinct question motivated by systems that evolve randomly over time and are subject to structural or resource constraints. Despite their diverse contexts, ranging from epidemic dynamics to queueing systems and influence propagation, the works share common analytical themes in the treatment of stochastic models, asymptotic behavior, and structural properties of optimal or equilibrium solutions. In the first problem, we develop a state-dependent epidemic model for the spread of infections across interacting population centers. Unlike classical mean-field approaches, the model directly characterizes the underlying stochastic dynamics and proves the existence of a sharp extinction threshold: when the curing rate exceeds this threshold, the expected extinction time scales logarithmically with the initial infection size, whereas below the threshold it diverges. The analysis yields clean asymptotic characterizations without mean-field approximations and extends to general weighted and asymmetric networks. The second problem considers the dynamic batching of online arrivals, a problem motivated by service systems and data-processing applications where larger batches enjoy economies of scale. The work formalizes the tradeoff between waiting costs and batch-processing efficiency and establishes both a polynomial-time offline optimal algorithm and a constant-competitive online algorithm that does not rely on distributional assumptions about arrivals. We also provide a lower bound on the competitive ratio for this problem that no online algorithm can beat. The third problem studies dynamic resource allocation with concave cost functions that capture user dissatisfaction from resource shortfalls. We analyze two non-convex optimization problems in this domain and present polynomial-time algorithms with provable guarantees on reaching their respective global optima. This utilizes techniques from optimization theory, queueing theory, and stochastic processes to overcome challenges from non-convexity and temporal dynamics. The final problem investigates influence maximization in social networks under general marketing strategies with budget constraints and partial incentives. We derive approximation guarantees for fast, greedy algorithms by using classical results on submodular function maximization, offering insights into optimal incentive allocation in heterogeneous populations. Although motivated by distinct applications, the problems studied here all address a central question: how should one reason about complex systems when randomness and limited information constrain what can be optimized or predicted? Each chapter explores a different manifestation of this question: extinction thresholds in epidemics, tradeoffs between delay and efficiency, non-convex resource allocation, and diffusion with partial incentives. Together, they highlight the unifying idea that a small set of mathematical principles can yield deep, transferable understanding of dynamical systems across disciplines.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Electrical & Computer Engr

Grantor

University of Illinois Urbana-Champaign

Year dc:date

2025

Author dc:creator

• Bhimaraju, Akhil

Contributors dc:contributor

• Varshney, Lav R
• Etesami, S. Rasoul
• Umrawal, Abhishek K
• Mittal, Radhika

• scheduling algorithms
• non-convex optimization
• resource allocation
• queuing
• networks
• online algorithms
• batching
• submodular functions

Statement dc:rights

• Copyright 2025 Akhil Bhimaraju

Language dc:language

en

Handle dc:identifier

https://hdl.handle.net/2142/132503

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/132503