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

 

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.

 

Talk 2 of the invited session Thu.2.H 3008
"Discrete structures and algorithms II" [...]
Cluster 2
"Combinatorial optimization" [...]

 

  Most online loan lenders allow getting New Jersey Payday Loans without visiting a bank, straight to your bank account. But at the same time, it acts only with sexual arousal. Cheap Viagra has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.