The request-trip-vehicle assignment problem is at the heart of a popular decomposition
strategy for online vehicle routing. In this framework, assignments are done in batches in …

We consider node-weighted network design problems, in particular the survivable network
design problem (SNDP) and its prize-collecting version (PC-SNDP). The input consists of a …

Abstract In the Steiner Network problem we are given a graph G with edge-costs and
connectivity requirements r uv between node pairs u, v. The goal is to find a minimum-cost …

In the Steiner Network problem, we are given a graph G with edge-costs and connectivity
requirements ruv between node pairs u, v. The goal is to find a minimum-cost subgraph H of …

We obtain polynomial-time approximation-preserving reductions (up to a factor of
1+\epsilon) from the prize-collecting Steiner tree and prize-collecting Steiner forest problems …

We consider node-weighted network design problems, in particular the survivable network
design problem SNDP and its prize-collecting version PC-SNDP. The input consists of a …

The Steiner Tree problem has appeared in the Karp's list of the first 21 NP-hard problems
and is well known as one of the most fundamental problems in Network Design area. We …

In this thesis, we consider combinatorial optimization problems involving submodular
functions and graphs. The problems we study are NP-hard and therefore, assuming that P≠ …

Abstract The Steiner Tree problem has appeared in the Karp's list of the first 21 NP-hard
problems and is well known as one of the most fundamental problems in Network Design …

Network design problems deal with settings where the goal is to design a network (ie, find a
subgraph of a given graph) that satisfies certain connectivity requirements. Each …