Network Design is an active research area in the intersection of Combinatorial Optimization
and Theoretical Computer Science that focuses on problems arising in the realm of modern …

With the advent of approximation algorithms for NP-hard combinatorial optimization
problems, several techniques from exact optimization such as the primal-dual method have …

In the Minimum Bounded Degree Spanning Tree problem, we are given an undirected
graph G=(V, E) with a degree upper bound Bv on each vertex v∈ V, and the task is to find a …

We present algorithmic and hardness results for network design problems with degree or
order constraints. We first consider the SURVIVABLE NETWORK DESIGN problem with …

We present polynomial-time approximation algorithms for some degree-bounded directed
network design problems. Our main result is for intersecting supermodular connectivity with …

We study the design of small cost temporally connected graphs, under various constraints.
We mainly consider undirected graphs of n vertices, where each edge has an associated set …

A natural way to deal with multiple, partially conflicting objectives is turning all the objectives
but one into budget constraints. Many classical optimization problems, such as maximum …

Modern parcel logistic networks are designed to ship demand between given origin,
destination pairs of nodes in an underlying directed network. Efficiency dictates that volume …

With the growth of model/dataset/system size for distributed model training in datacenters,
the widely used Parameter Server (PS) architecture suffers from communication bottleneck …

We present a 6-approximation algorithm for the minimum-cost k-node connected spanning
subgraph problem, assuming that the number of nodes is at least k^3(k-1)+k. We apply a …