We consider a new combinatorial optimization problem that combines network design and facility location aspects. Given a graph with two types of customers and two technologies that can be installed on the edges, the objective is to find a minimum cost subtree connecting all customers while the...

We consider a network design problem that arises in the cost-optimal design of last mile telecommunication networks. It extends the Connected Facility Location problem by introducing capacities on the facilities and links of the networks. It combines aspects of the capacitated network design...

Given a point on the standard simplex, we calculate a proximal point on the regular grid which is closest with respect to any norm in a large class, including all <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$$\ell ^p$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <msup> <mi>ℓ</mi> <mi>p</mi> </msup> </math> </EquationSource> </InlineEquation>-norms for <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$$p\ge 1$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <mrow> <mi>p</mi> <mo>≥</mo> <mn>1</mn> </mrow> </math> </EquationSource> </InlineEquation>. We show that the minimal <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$$\ell ^p$$</EquationSource> <EquationSource Format="MATHML"> <math xmlns:xlink="http://www.w3.org/1999/xlink"> <msup> <mi>ℓ</mi> <mi>p</mi> </msup> </math> </EquationSource> </InlineEquation>-distance to the...</equationsource></equationsource></inlineequation></equationsource></equationsource></inlineequation></equationsource></equationsource></inlineequation>

We consider a network design problem that generalizes the hop and diameter constrained Steiner tree problem as follows: Given an edge-weighted undirected graph with two disjoint subsets representing roots and terminals, find a minimum-weight subtree that spans all the roots and terminals so that...

This paper presents a new combinatorial optimization problem that can be used to model the deployment of broadband telecommunications systems in which optical fiber cables are installed between a central office and a number of end-customers. In this capacitated network design problem the...

In the Prize-Collecting Steiner Tree Problem (PCStT) we are given a set of customers with potential revenues and a set of possible links connecting these customers with fixed installation costs. The goal is to decide which customers to connect into a tree structure so that the sum of the link...