## 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**

**Abstract:**

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**

**Abstract:**

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.