We study the two most common types of percolation processes on a sparse random graph
with a given degree sequence. Namely, we examine first a bond percolation process where …

A rectangulation is a decomposition of a rectangle into finitely many rectangles. Via natural
equivalence relations, rectangulations can be seen as combinatorial objects with a rich …

Attempts to allow exponentially many inequalities to be candidates to Lagrangian
dualization date from the early 1980's. In this paper, the term Relax-and-Cut, introduced …

A Lagrangian based exact solution algorithm for the vehicle routing problem (VRP), defined
on an undirected graph, is introduced in this paper. Lower bounds are obtained by allowing …

A floorplan is a tiling of a rectangle by rectangles. There are natural ways to order the
elements---rectangles and segments---of a floorplan. Ackerman, Barequet and Pinter …

In this chapter, we discuss the principle of decomposition as it applies to the computation of
bounds on the value of an optimal solution to an integer linear program (ILP). Most bounding …

We investigate the number of different ways in which a rectangle containing a set of n
noncorectilinear points can be partitioned into smaller rectangles by n (nonintersecting) …

Finding maximum weight connected subgraphs within networks is a fundamental
combinatorial optimization problem both from theoretical and practical standpoints. One of …

In this paper, we propose a Lagrangian Non‐Delayed Relax‐and‐Cut algorithm for the
Degree‐Constrained Minimum Spanning Tree Problem (DCMSTP). Since degree …

Decomposition algorithms such as Lagrangian relaxation and Dantzig-Wolfe decomposition
are well-known methods that can be used to generate bounds for mixed-integer linear …