An official website of the United States government
Abstract We introduce partitioned matching games as a suitable model for international kidney exchange programmes, where in each round the total number of available kidney transplants needs to be distributed amongst the participating countries in a “fair” way. A partitioned matching game (N, v) is defined on a graph$$G=(V,E)$$ with an edge weightingwand a partition$$V=V_1 \cup \dots \cup V_n$$ . The player set is$$N = \{ 1, \dots , n\}$$ , and player$$p \in N$$ owns the vertices in$$V_p$$ . The valuev(S) of a coalition $$S \subseteq N$$ is the maximum weight of a matching in the subgraph ofGinduced by the vertices owned by the players in S. If$$|V_p|=1$$ for all$$p\in N$$ , then we obtain the classical matching game. Let$$c=\max \{|V_p| \; |\; 1\le p\le n\}$$ be the width of (N, v). We prove that checking core non-emptiness is polynomial-time solvable if$$c\le 2$$ but co--hard if$$c\le 3$$ . We do this via pinpointing a relationship with the known class ofb-matching games and completing the complexity classification on testing core non-emptiness forb-matching games. With respect to our application, we prove a number of complexity results on choosing, out of possibly many optimal solutions, one that leads to a kidney transplant distribution that is as close as possible to some prescribed fair distribution.
more »
« less
A folding preprocess for the max k-cut problem
Abstract Given graph$$G=(V,E)$$ with vertex setVand edge setE, the maxk-cut problem seeks to partition the vertex setVinto at mostksubsets that maximize the weight (number) of edges with endpoints in different parts. This paper proposes a graph folding procedure (i.e., a procedure that reduces the number of the vertices and edges of graphG) for the weighted maxk-cut problem that may help reduce the problem’s dimensionality. While our theoretical results hold for any$$k \ge 2$$ , our computational results show the effectiveness of the proposed preprocessonlyfor$$k=2$$ and on two sets of instances. Furthermore, we observe that the preprocess improves the performance of a MIP solver on a set of large-scale instances of the max cut problem.
more »
« less
- Award ID(s):
- 2318790
- PAR ID:
- 10585913
- Publisher / Repository:
- Springer Science + Business Media
- Date Published:
- Journal Name:
- Optimization Letters
- Volume:
- 19
- Issue:
- 5
- ISSN:
- 1862-4472
- Format(s):
- Medium: X Size: p. 899-917
- Size(s):
- p. 899-917
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract In the spanning tree congestion problem, given a connected graphG, the objective is to compute a spanning treeTinGthat minimizes its maximum edge congestion, where the congestion of an edgeeofTis the number of edges inGfor which the unique path inTbetween their endpoints traversese. The problem is known to be$$\mathbb{N}\mathbb{P}$$ -hard, but its approximability is still poorly understood, and it is not even known whether the optimum solution can be efficiently approximated with ratioo(n). In the decision version of this problem, denoted$${\varvec{K}-\textsf {STC}}$$ , we need to determine ifGhas a spanning tree with congestion at mostK. It is known that$${\varvec{K}-\textsf {STC}}$$ is$$\mathbb{N}\mathbb{P}$$ -complete for$$K\ge 8$$ , and this implies a lower bound of 1.125 on the approximation ratio of minimizing congestion. On the other hand,$${\varvec{3}-\textsf {STC}}$$ can be solved in polynomial time, with the complexity status of this problem for$$K\in { \left\{ 4,5,6,7 \right\} }$$ remaining an open problem. We substantially improve the earlier hardness results by proving that$${\varvec{K}-\textsf {STC}}$$ is$$\mathbb{N}\mathbb{P}$$ -complete for$$K\ge 5$$ . This leaves only the case$$K=4$$ open, and improves the lower bound on the approximation ratio to 1.2. Motivated by evidence that minimizing congestion is hard even for graphs of small constant radius, we also consider$${\varvec{K}-\textsf {STC}}$$ restricted to graphs of radius 2, and we prove that this variant is$$\mathbb{N}\mathbb{P}$$ -complete for all$$K\ge 6$$ .more » « less
-
Abstract The minimum linear ordering problem (MLOP) generalizes well-known combinatorial optimization problems such as minimum linear arrangement and minimum sum set cover. MLOP seeks to minimize an aggregated cost$$f(\cdot )$$ due to an ordering$$\sigma $$ of the items (say [n]), i.e.,$$\min _{\sigma } \sum _{i\in [n]} f(E_{i,\sigma })$$ , where$$E_{i,\sigma }$$ is the set of items mapped by$$\sigma $$ to indices [i]. Despite an extensive literature on MLOP variants and approximations for these, it was unclear whether the graphic matroid MLOP was NP-hard. We settle this question through non-trivial reductions from mininimum latency vertex cover and minimum sum vertex cover problems. We further propose a new combinatorial algorithm for approximating monotone submodular MLOP, using the theory of principal partitions. This is in contrast to the rounding algorithm by Iwata et al. (in: APPROX, 2012), using Lovász extension of submodular functions. We show a$$(2-\frac{1+\ell _{f}}{1+|E|})$$ -approximation for monotone submodular MLOP where$$\ell _{f}=\frac{f(E)}{\max _{x\in E}f(\{x\})}$$ satisfies$$1 \le \ell _f \le |E|$$ . Our theory provides new approximation bounds for special cases of the problem, in particular a$$(2-\frac{1+r(E)}{1+|E|})$$ -approximation for the matroid MLOP, where$$f = r$$ is the rank function of a matroid. We further show that minimum latency vertex cover is$$\frac{4}{3}$$ -approximable, by which we also lower bound the integrality gap of its natural LP relaxation, which might be of independent interest.more » « less
-
Abstract Given integers$$n> k > 0$$ , and a set of integers$$L \subset [0, k-1]$$ , anL-systemis a family of sets$$\mathcal {F}\subset \left( {\begin{array}{c}[n]\\ k\end{array}}\right) $$ such that$$|F \cap F'| \in L$$ for distinct$$F, F'\in \mathcal {F}$$ .L-systems correspond to independent sets in a certain generalized Johnson graphG(n, k, L), so that the maximum size of anL-system is equivalent to finding the independence number of the graphG(n, k, L). TheLovász number$$\vartheta (G)$$ is a semidefinite programming approximation of the independence number$$\alpha $$ of a graphG. In this paper, we determine the leading order term of$$\vartheta (G(n, k, L))$$ of any generalized Johnson graph withkandLfixed and$$n\rightarrow \infty $$ . As an application of this theorem, we give an explicit construction of a graphGonnvertices with a large gap between the Lovász number and the Shannon capacityc(G). Specifically, we prove that for any$$\epsilon > 0$$ , for infinitely manynthere is a generalized Johnson graphGonnvertices which has ratio$$\vartheta (G)/c(G) = \Omega (n^{1-\epsilon })$$ , which improves on all known constructions. The graphGa fortiorialso has ratio$$\vartheta (G)/\alpha (G) = \Omega (n^{1-\epsilon })$$ , which greatly improves on the best known explicit construction.more » « less
-
Abstract We construct an example of a group$$G = \mathbb {Z}^2 \times G_0$$ for a finite abelian group $$G_0$$ , a subsetEof $$G_0$$ , and two finite subsets$$F_1,F_2$$ of G, such that it is undecidable in ZFC whether$$\mathbb {Z}^2\times E$$ can be tiled by translations of$$F_1,F_2$$ . In particular, this implies that this tiling problem isaperiodic, in the sense that (in the standard universe of ZFC) there exist translational tilings ofEby the tiles$$F_1,F_2$$ , but no periodic tilings. Previously, such aperiodic or undecidable translational tilings were only constructed for sets of eleven or more tiles (mostly in $$\mathbb {Z}^2$$ ). A similar construction also applies for$$G=\mathbb {Z}^d$$ for sufficiently large d. If one allows the group$$G_0$$ to be non-abelian, a variant of the construction produces an undecidable translational tiling with only one tile F. The argument proceeds by first observing that a single tiling equation is able to encode an arbitrary system of tiling equations, which in turn can encode an arbitrary system of certain functional equations once one has two or more tiles. In particular, one can use two tiles to encode tiling problems for an arbitrary number of tiles.more » « less
