Optimization problems in networks and queues

Bhimaraju, Akhil

Permalink

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

Description

Title

Optimization problems in networks and queues

Author(s)

Bhimaraju, Akhil

Issue Date

2025-12-04

Director of Research (if dissertation) or Advisor (if thesis)

Varshney, Lav R

Doctoral Committee Chair(s)

Varshney, Lav R

Committee Member(s)

• Etesami, S. Rasoul
• Umrawal, Abhishek K
• Mittal, Radhika

Department of Study

Electrical & Computer Eng

Discipline

Electrical & Computer Engr

Degree Granting Institution

University of Illinois Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

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

Abstract

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.

Graduation Semester

2025-12

Type of Resource

Thesis

Handle URL

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

Copyright and License Information

Copyright 2025 Akhil Bhimaraju

Owning Collections