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.


  There are three major facts that should be watched out for in all payday loans in the United States. But it is worth noting that these tests were carried out on the blood cells. Therefore, it's too early to say about scientific evidence of Viagra No RX influence on blood clots.