Contributed Session Tue.3.H 3012

Tuesday, 15:15 - 16:45 h, Room: H 3012

Cluster 2: Combinatorial optimization [...]

LP relaxations


Chair: Dorit S. Hochbaum



Tuesday, 15:15 - 15:40 h, Room: H 3012, Talk 1

Maria Teresa Godinho
On a time-dependent formulation for the travelling salesman problem

Coauthors: Luís Gouveia, Pierre Pesneau


In the past, several papers have produced a classification of formulations for the ATSP, in terms of the associated linear programming relaxations. Among others, we may consider the papers by Gouveia and Voss (1995), Langevin et al (1990), Gouveia and Pires (1999), Orman and Williams (2007) and Oncan et al (2009). These papers fall among two classes. Either they produce new results between formulations known from the literature, or they use the fact that new formulations are also being presented in the paper in order to upgrade a classification already known from the literature.
Our talks falls in the second category in the sense that we present an updated classification of formulations for the asymmetric travelling salesman problem (ATSP)where we contextualize, in terms of the ATSP, a new time-dependent formulation presented in Godinho et al (2010).
The main feature of this formulation is that it uses, for each node, a stronger subproblem, namely a n-circuit subproblem with the additional constraint that the corresponding node is not repeated in the circuit.



Tuesday, 15:45 - 16:10 h, Room: H 3012, Talk 2

Dorit S. Hochbaum
Flow-based algorithms that solve clustering problems related to graph expander, normalized cut and conductance better than the spectral method


We address challenging problems in clustering, partitioning and imaging including the normalized cut
problem, graph expander, Cheeger constant problem and conductance problem. These have traditionally
been solved using the "spectral technique''. These problems are formulated here as a quadratic
ratio (Rayleigh) with discrete constraints and a single sum constraint. The spectral method solves
a relaxation that omits the discreteness constraints. A new relaxation, that omits the sum
constraint, is shown to be solvable in strongly polynomial time. It is shown, via an experimental
study, that the bipartition achieved by the combinatorial algorithm often improve dramatically in
terms of the objective value of the respective NP-hard problem, as well as in terms of the visual
quality of the segmentation, compared to the spectral method in image segmentation and image
denoising instances.



Tuesday, 16:15 - 16:40 h, Room: H 3012, Talk 3

Yong-Hong Kuo
On the mixed set covering, partitioning and packing problem

Coauthor: Janny M. Y. Leung


Set covering, set partitioning and set packing problems have already been studied for more than 40 years. However, researchers usually consider the problems individually and very few literatures have mentioned the mixed set covering, partitioning and packing problem, where the three kinds of constraints are present simultaneously in the formulation. The problems with such kind of structures play an important role in the real-life applications, e.g., staff scheduling problems. In this talk, we will discuss the polyhedral structure of the problem and present a way, which we call "implicit edges generation'' approach, to further tighten the feasible region and, as a result, makes the LP optimal closer to the IP optimal. We will also present some classes of facet-defining inequalities produced by this approach. Computational results show that, using our proposed methodology, a tighter formulation can be obtained and, consequently significant reductions of computational efforts are made.


  There are three major facts that should be watched out for in all payday loans in the United States. Since its introduction in the market buying Cialis can be exclusively in pharmacy chains with a prescription from a doctor. I agree that this is very inconvenient and takes a lot of time and effort.