Contributed Session Wed.1.H 2033

Wednesday, 10:30 - 12:00 h, Room: H 2033

Cluster 11: Integer & mixed-integer programming [...]

Assignments and partitioning


Chair: Trivikram Dokka



Wednesday, 10:30 - 10:55 h, Room: H 2033, Talk 1

Ya Ju Fan
A heuristic for the local region covering problem

Coauthor: Chandrika Kamath


The topological or local dimension of a data manifold can be obtained using local methods, where the data are divided into smaller regions. The original Fukunaga-Olsen algorithm for the intrinsic dimension of a dataset used heuristic approaches to identify the smaller regions. To obtain an improved partitioning of the data space, we formulate this problem as a set covering problem, where each local region contains the k nearest neighbors of a data point. We discuss how we define the cost function to obtain an estimation based on a fair selection of local regions. This problem can be seen as a facility location problem with the number of facilities being optimized in order to maintain the service to at most k cities per facility. To solve the local region problem, we present a simple and easy to implement heuristic method that is a variant of a greedy approach.



Wednesday, 11:00 - 11:25 h, Room: H 2033, Talk 2

Trivikram Dokka
Fast separation algorithms for multi-dimensional assignment problems

Coauthors: Ioannis Mourtos, Frits Spieksma


In polyhedral combinatorics, the polytope related to a combinatorial optimization problem is examined in order to obtain families of strong valid inequalities or, even better, to find inequalities that are facet-defining for this polytope. To incorporate such families of inequalities within a `branch & cut' algorithm requires one further step: that of deriving an algorithm which determines whether an inequality of a specific family is violated by a given vector (the separation problem). The idea put forward in this work is to consider a compact representation of the given vector, and measure the complexity of a separation algorithm in terms of this compact representation. We illustrate this idea on the separation
problem of well-known families of inequalities associated to the (multi-index) assignment polytope, and we show that for these families of inequalities better time-complexities than the current ones are possible.


  online loans . But at the same time, it acts only with sexual arousal. Viagra has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.