## Invited Session Thu.2.H 3008

#### Thursday, 13:15 - 14:45 h, Room: H 3008

**Cluster 2: Combinatorial optimization** [...]

### Discrete structures and algorithms II

**Chair: Satoru Fujishige**

**Thursday, 13:15 - 13:40 h, Room: H 3008, Talk 1**

**Akiyoshi Shioura**

Computing the convex closure of discrete convex functions

**Abstract:**

We consider computational aspect of the convex closure of discrete

convex functions. More precisely, given a discrete convex function

defined on the integer lattice, we consider an algorithm for computing

the function value and a subgradient of the convex closure at a given

point. Such an algorithm is required when the continuous relaxation

approach is applied to nonlinear integer programs. In the theory of

discrete convex analysis, two classes of discrete convex functions

called M-/L-convex functions play primary roles; an M-convex function

is a function defined on an integral polymatroid, while an L-convex

function can be seen as an extension of a submodular set function.

While the convex closure of an L-convex function can be expressed by a

simple formula, it is not clear how to compute the convex closure of

an M-convex function. In this talk, we show that the function values

and subgradients of the convex closure of an M-convex function can be

computed efficiently. This result is shown by making full use of

conjugacy results of discrete convex analysis.

**Thursday, 13:45 - 14:10 h, Room: H 3008, Talk 2**

**Naoyuki Kamiyama**

Matroid intersection with priority constraints

**Abstract:**

In this paper, we consider the following variant of the matroid intersection problem. We are given two matroids *M*_{1} and *M*_{2} on the same ground set *S* and a subset *A* of *S*. Our goal is to find a common independent set *I* of *M*_{1} and *M*_{2} such that *|I ∩ A|* is maximum among all common independent sets of *M*_{1} and *M*_{2} and such that (secondly) *|I|* is maximum among all common independent sets of *M*_{1} and *M*_{2} satisfying the first condition. This problem can be solved by reducing it to the weighted matroid intersection problem.

In this paper, we consider the following

question: Is reduction to the weighted matroid intersection is inevitable? We prove that our problem can be solved by using a Dulmage-Mendelsohn decomposition without reduction to the weighted matroid intersection problem.

**Thursday, 14:15 - 14:40 h, Room: H 3008, Talk 3**

**Britta Peis**

Resource buying games

**Coauthor: Tobias Harks**

**Abstract:**

In resource buying games, players jointly buy a subset of a given resource set. As in classical congestion games, each player has a predefined family of subsets of the resources from which she needs at least one to be available. However, a resource is only available if the sum of payments of all players cover the load-dependent cost of that resource. A strategy of a player is therefore a tupel consisting of one of her resource sets together with a payment vector indicating how much she is willing to contribute towards the purchase of each resource. During the talk, we study the existence and computability of pure Nash equilibria (PNEs) in resource buying games.

Resource buying games reduce to connection games in the special case where the costs are fixed and the players' resource sets are

network-paths connecting two player-specific terminals,

While there exist very simple connection games without PNE, we will see that PNEs exist and can be efficiently computed if each player's strategy set is the base set of a matroid and the marginal cost of each resource is monotone.