Source author record

Stefan Kober

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Discrete Mathematics math.OC Computer Science and Game Theory Data Structures and Algorithms math.CO

Catalog footprint

Research overview

2works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2023arXiv

Total Matching and Subdeterminants

In the total matching problem, one is given a graph $G$ with weights on the vertices and edges. The goal is to find a maximum weight set of vertices and edges that is the non-incident union of a stable set and a matching. We consider the natural formulation of the problem as an integer program (IP), with variables corresponding to vertices and edges. Let $M = M(G)$ denote the constraint matrix of this IP. We define $Δ(G)$ as the maximum absolute value of the determinant of a square submatrix of $M$ . We show that the total matching problem can be solved in strongly polynomial time provided $Δ(G) \leq Δ$ for some constant $Δ\in \mathbb{Z}_{\ge 1}$ . We also show that the problem of computing $Δ(G)$ admits an FPT algorithm. We also establish further results on $Δ(G)$ when $G$ is a forest.

preprint2020arXiv

Improved lower bound on the dimension of the EU council's voting rules

Kurz and Napel (2015) proved that the voting system of the EU council (based on the 2014 population data) cannot be represented as the intersection of six weighted games, i.e., its dimension is at least 7. This set a new record for real-world voting rules and the authors posed the exact determination as a challenge. Recently, Chen, Cheung, and Ng (2019) showed that the dimension is at most 24. We provide the first improved lower bound and show that the dimension is at least 8.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.