Zobrazeno 1 - 10
of 27
pro vyhledávání: '"Beideman, Calvin"'
We show that every $\alpha$-approximate minimum cut in a connected graph is the unique minimum $(S,T)$-terminal cut for some subsets $S$ and $T$ of vertices each of size at most $\lfloor2\alpha\rfloor+1$. This leads to an alternative proof that the n
Externí odkaz:
http://arxiv.org/abs/2211.16747
We consider the problem of enumerating optimal solutions for two hypergraph $k$-partitioning problems -- namely, Hypergraph-$k$-Cut and Minmax-Hypergraph-$k$-Partition. The input in hypergraph $k$-partitioning problems is a hypergraph $G=(V, E)$ with
Externí odkaz:
http://arxiv.org/abs/2204.09178
We consider the problem of deterministically enumerating all minimum $k$-cut-sets in a given hypergraph for any fixed $k$. The input here is a hypergraph $G = (V, E)$ with non-negative hyperedge costs. A subset $F$ of hyperedges is a $k$-cut-set if t
Externí odkaz:
http://arxiv.org/abs/2110.14815
We design an algorithm for computing connectivity in hypergraphs which runs in time $\hat O_r(p + \min\{\lambda^{\frac{r-3}{r-1}} n^2, n^r/\lambda^{r/(r-1)}\})$ (the $\hat O_r(\cdot)$ hides the terms subpolynomial in the main parameter and terms that
Externí odkaz:
http://arxiv.org/abs/2011.08097
We address counting and optimization variants of multicriteria global min-cut and size-constrained min-$k$-cut in hypergraphs. 1. For an $r$-rank $n$-vertex hypergraph endowed with $t$ hyperedge-cost functions, we show that the number of multiobjecti
Externí odkaz:
http://arxiv.org/abs/2006.11589
Autor:
Beideman, Calvin1 (AUTHOR) calvinb2@illinois.edu, Chandrasekaran, Karthekeyan1 (AUTHOR) karthe@illinois.edu, Wang, Weihang1 (AUTHOR) weihang3@illinois.edu
Publikováno v:
Mathematics of Operations Research. Nov2024, Vol. 49 Issue 4, p2579-2601. 23p.
We analyze the Sprague-Grundy functions for a class of almost disjoint selective compound games played on Nim heaps. Surprisingly, we find that these functions behave chaotically for smaller Sprague-Grundy values of each component game yet predictabl
Externí odkaz:
http://arxiv.org/abs/1802.08700
Autor:
Beideman, Calvin1 (AUTHOR), Chandrasekaran, Karthekeyan1 (AUTHOR) karthe@illinois.edu, Wang, Weihang1 (AUTHOR)
Publikováno v:
Mathematical Programming. Sep2024, Vol. 207 Issue 1/2, p329-367. 39p.
Autor:
Beideman, Calvin, Blocki, Jeremiah
A $\left(n,\ell,\gamma\right)$-sharing set family of size $m$ is a family of sets $S_1,\ldots,S_m\subseteq [n]$ s.t. each set has size $\ell$ and each pair of sets shares at most $\gamma$ elements. We let $m\left(n,\ell,\gamma\right)$ denote the maxi
Externí odkaz:
http://arxiv.org/abs/1404.4622
Autor:
Beideman, Calvin1 (AUTHOR), Chandrasekaran, Karthekeyan1 (AUTHOR) karthe@illinois.edu, Xu, Chao2 (AUTHOR)
Publikováno v:
Mathematical Programming. Jan2023, Vol. 197 Issue 1, p27-69. 43p.