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 M1 and M2 on the same ground set S and a subset A of S. Our goal is to find a common independent set I of M1 and M2 such that |I ∩ A| is maximum among all common independent sets of M1 and M2 and such that (secondly) |I| is maximum among all common independent sets of M1 and M2 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.

 

  There are three major facts that should be watched out for in all payday loans in the United States. On the global pharmaceutical market this medicine was issued in 2003 by two companies - Eli Lilly and ICOS. Initially, permission to sell Cialis was obtained in Europe, Australia, New Zealand.