Publications by Thomas Liebling

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

We consider the school bus routing and scheduling problem, where transportation demand is known and bus scheduling can be planned in advance. We present a comprehensive methodology designed to support the decision of practitioners. We first propose a modeling framework where the focus is on optimizing the level of service for a given number of buses. Then, we describe an automatic procedure generating a solution to the problem. It first builds a feasible solution, which is subsequently improved using a heur

Meshes with (recursive) subdivision connectivity, such as subdivision surfaces, are increasingly popular in computer graphics. They present several advantages over their Delaunay-type based counterparts, e.g., Triangulated Irregular Networks (TINs), such as efficient processing, compact storage and numerical robustness. A mesh having subdivision connectivity can be described using a tree structure and recent work exploits this inherent hierarchy in applications such as progressive terrain visualization, sur

In this paper we address the problem of computing a minimal representation of the convex hull of the union of k H- polytopes in . Our method applies the reverse search algorithm to a shelling ordering of the facets of the convex hull. Efficient wrapping is done by projecting the polytopes onto the two-dimensional space and solving a linear program. The resulting algorithm is polynomial in the sizes of input and output under the general position assumption.

The basic concepts of a deterministic model for simulating grain growth or foam coarsening in two dimensions are presented, and the fundamental tools necessary for its implementation into computer codes are provided. It is assumed that the actual cell structure can be satisfactorily represented by a Laguerre (or weighted Voronoi) diagram, entirely determined by a collection of weighted sites or circles. The cellular motion (including the induced elementary topological transformations) is subjected to the mo

We describe an approach for exploring microscopic properties of granular media that couples x-ray microtomography and distinct-element-method (DEM) simulations through image analysis. We illustrate it via the study of the intriguing phenomenon of instant a ...

The placement of telecommunication satellites in the geostationary orbit (GSO) gives rise to NP-hard optimization problems usually approached with iterative neighborhood (possibly tabu) search schemes. A typical iteration thereof consist in fixing an order for the satellites and determining their actual location by linear programming. In such procedures it is crucial to efficiently solve the very large number of arising special linear programs. We describe those linear preograms, characterize their duals as

We deal with non-rank facets of the stable set polytope of claw-free graphs. We extend results of Giles and Trotter [7] by (i) showing that for any nonnegative integer a there exists a circulant graph whose stable set polytope has a facet-inducing inequality with (a,a+1)-valued coefficients (rank facets have only coefficients 0, 1), and (ii) providing new facets of the stable set polytope with up to five different non-zero coefficients for claw-free graphs. We prove that coefficients have to be consecutive

In this paper we present a heuristic algorithm for the well- known Unconstrained Quadratic 0–1 Programming Problem. The approach is based on combining solutions in a genetic paradigm and incorporates intensification algorithms used to improve solutions and speed up the method. Extensive computational experiments on instances with up to 500 variables are presented and we compare our approach both with powerful heuristic and exact algorithms from the literature establishing the effectiveness of the method in

We deal with non-rank facets of the stable set polytope of claw-free graphs. We extend results of Gilles and Trotter (7) by (i) showing that for any nonnegative integer a there exists a circulant graph whose stable set polytope has a facet-inducing inequality with (a,a+1) valued coefficinets (rank facets have onnly coefficients 0, 1), and (ii) providing new facets of the stable set polytope with up to five different non-zero coefficients for claw-free graphs. We prove that coefficients have to be consecutiv

Colliding beams experiments High Energy Physics rely on solid state detectors to track the flight paths of charged elementary particles near their primary point of interaction. Reconstructing tracks in this region requires, per collision, a partitioning of up to 10^3 highly correlated observations into an unknown number of tracks. We report on the succesful implementation of a combinatorial track finding algorithm to solve this pattern recognition problem in the context of the ALEPH experiment ar CERN. Cent

The basic concepts of a deterministic scheme for simulating grain growth or foam coarsening in two dimensions have been presented in Part I. Implementation of the corresponding Laguerre (or weighted Voronoi) diagram in computer manageable practical terms is now presented. The internal constituents of the model are discussed first and include the initial configurations of the cellular network, obtained from different schemes. An internal clock is designed and an arbitrary dimensionless parameter is introduce

We consider the problem of finding an optimal family of nested rooted subtrees of a tree. We give a linear algorithm for the associated 1.p. for this problem. A generalization of this problem is that of finding an optimal "lower closed set" of nodes in an acyclic graph for which polyhedral and polarity characterization are given. these problem are useful relaxations when solving more complicated sequencing problems.

2D-CELL is a software package for the processing and analyzing of photographic images of cellular structures in a largely interactive way. Starting from a binary digitized image, the programs extract the line network (skeleton) of the structure and determine the graph representation that best models it. Provision is made for manually correcting defects such as incorrect node positions or dangling bonds. Then a suitable algorithm retrieves polygonal contours which define individual cells — local boundary cur

We address the weighted max-cut problem, or equivalently the problem of maximizing a quadratic form in n binary variables. If the underlying (symmetric) matrix is positive semidefinite of fixed rank d, then the problem can be reduced to searching the extreme points of a zonotope, thus becoming of polynomial complexity in O(nd - 1). Reverse search is an efficient and practical means for enumerating the cells of a regular hyperplane arrangement, or equivalently, the extreme points of a zonotope. We present an

Having briefly recalled both approaches for simulating 2-D grain growth published by the other groups, we outline a third one. It consists of unit topological changes occurrins at the microscopic level. Preliminary results are presented. Is is argued that further improvements will result from a revised expression of the total energy of the system that takes into account the tendency to equilibrate local forces at grain corners.

Computer simulations of granular materials based on the distinct element method (DEM) are now commonly used in the design and optimization of industrial processes. One of the leading mathematical approach to DEM uses dynamic triangulations for detecting collisions among moving spheres, and relies on advanced data structures and on the exact numerical evaluation of computational geometry predicates. This paper outlines the simulation method and introduces the robust and adaptive computation of predicates usi

Laguerre diagrams are used as a geometric idealization of 3-dimensional polycrystals. These cell structures are entirely defined by a set of weighted sites. Each site is given an additional weight which affects the size of the associated cell. Models of growth can be constructed for this idealized polycrystal geometry by writing the motion equation in terms of the weighted sites alone. In computer simulation, the solution of non-linear differential system is approximated by piecewise linear motions. During

We study order preserving injections or bipartite matchings from poset V1 to poset V2. When V1 is totally ordered, we give an efficient algorithm for the associated optimization problem and the convex hull of the corresponding characteristic vectors. If V2 is totally ordered and V1 is not, the problem is NP-complete.

Thomas Liebling

Chat with Graph Search

Decision-aid Methodology for the school Bus Routing and Scheduling Problem

Mesh Optimization Using Global Error with Application to Geometry Simplification

Computational Analysis of Mesh Simplification Using Global Error

Extended convex hull

The Laguerre model of grain growth in two dimensions I. Cellular structures viewed as dynamical Laguerre tessellations

Coupled tomography and distinct-element-method approach to exploring the granular media microstructure in a jamming hourglass

Decision-aid methodology for the school bus routing and scheduling problem

Modeling the satellite placement problem as a network flow problem with one side constraint

On non-rank facets of the stable set polytope of claw-free graphs and circulant graphs

An evolutionary heuristic for quadratic 0-1 programming

on Non-Rank Facets of the Stable Set Polytope of Claw-Free Graphs and Circulant Graphs

Tracking elementary particles near their primary vertex: a combinatorial approach

The Laguerre model of grain growth in two dimensions II. Examples of coarsening simulations

Optimal subtrees and extensions

2D-CELL: image processing software for extraction and analysis of 2-dimensional cellular structures

Solving the fixed rank convex quadratic maximization in binary variables by a parallel zonotope construction algorithm

Simulation of grain growth in 2-Dimensions: influence of the energy expression for the grain boundary network

Robust 3D Dynamic Triangulations for Collision Detection in DEM Simulations of Granular Materials

First results on 3-D simulation grain growth using Laguerre diagrams

A note on order preserving matchings