Zobrazeno 1 - 10
of 58
pro vyhledávání: '"R. Chestnut"'
Autor:
Rico Zenklusen, Stephen R. Chestnut
Publikováno v:
Networks. 69:378-387
In the Network Flow Interdiction problem, an adversary attacks a network in order to minimize the maximum s-t-flow. Very little is known about the approximatibility of this problem, despite decades of interest in it. It is, surprisingly, nontrivial t
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::4b68f7c3a978a40168c6aaf8340a8feb
https://doi.org/10.1002/net.21739
https://doi.org/10.1002/net.21739
Autor:
Stephen R. Chestnut, Rico Zenklusen
Publikováno v:
Mathematics of Operations Research. 42:144-166
Interdiction problems ask about the worst-case impact of a limited change to an underlying optimization problem. They are a natural way to measure the robustness of a system, or to identify its weakest spots. Interdiction problems have been studied f
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::653d9b1227abfa839835873a6e4d0a66
https://doi.org/10.1287/moor.2016.0798
https://doi.org/10.1287/moor.2016.0798
Publikováno v:
Operations Research Letters. 44:766-771
In 2006, Goemans presented an approximation algorithm for the minimum bounded degree spanning tree problem that constructs a tree with cost at most the optimal value of an LP relaxation but degree bound violations of up to two units per vertex. He co
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::33ca96d3482e8cb40ec0792b76a063c7
https://doi.org/10.1016/j.orl.2016.09.014
https://doi.org/10.1016/j.orl.2016.09.014
Autor:
Jelani Nelson, David P. Woodruff, Vladimir Braverman, Nikita Ivkin, Stephen R. Chestnut, Zhengyu Wang
Publikováno v:
PODS
The task of finding heavy hitters is one of the best known and well studied problems in the area of data streams. One is given a list i1,i2,...,im∈[n] and the goal is to identify the items among [n] that appear frequently in the list. In sub-polyno
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::03625aaef2bff45dcc50770f25ea6ea8
https://doi.org/10.1145/3034786.3034798
https://doi.org/10.1145/3034786.3034798
Publikováno v:
PODS
A central problem in the theory of algorithms for data streams is to determine which functions on a stream can be approximated in sublinear, and especially sub-polynomial or poly-logarithmic, space. Given a function $g$, we study the space complexity
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::167c3916dec04a9c83851ab4aeb639a7
Publikováno v:
STOC
We characterize the streaming space complexity of every symmetric norm $l$ (a norm on $\mathbb{R}^n$ invariant under sign-flips and coordinate-permutations), by relating this space complexity to the measure-concentration characteristics of $l$. Speci
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::4fbec4acd60a9098f808227c05dd59c1
http://arxiv.org/abs/1511.01111
http://arxiv.org/abs/1511.01111
Publikováno v:
SIAM Journal on Discrete Mathematics, 32 (1)
The recent paper A Quantitative Doignon-Bell-Scarf Theorem by Aliev et al. [Combinatorica, 37 (2017), pp. 313--332] generalizes the famous Doignon--Bell--Scarf theorem on the existence of integer solutions to systems of linear inequalities. Their gen
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::4efa7d3de4d7061da0386e66673afe18
Publikováno v:
STOC
Given a stream $p_1, \ldots, p_m$ of items from a universe $\mathcal{U}$, which, without loss of generality we identify with the set of integers $\{1, 2, \ldots, n\}$, we consider the problem of returning all $\ell_2$-heavy hitters, i.e., those items
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::5ce290cf55a136d1b3ffd11e78b6731f
Autor:
Manuel E. Lladser, Stephen R. Chestnut
Publikováno v:
Journal of mathematical biology. 69(1)
Sojourn-times provide a versatile framework to assess the statistical significance of motifs in genome-wide searches even under non-Markovian background models. However, the large state spaces encountered in genomic sequence analyses make the exact c
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::a4d38b36712a947d016b7e4fa3709e0e
https://pubmed.ncbi.nlm.nih.gov/23739838
https://pubmed.ncbi.nlm.nih.gov/23739838
Autor:
Manuel E. Lladser, Stephen R. Chestnut
We state and prove new properties about Doeblin's ergodicity coefficient for finite Markov chains. We show that this coefficient satisfies a sub-multiplicative type inequality (analogous to the Markov-Dobrushin's ergodicity coefficient), and provide
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0e478da0187454ecb291c39c8a1c4360
https://dmtcs.episciences.org/2789
https://dmtcs.episciences.org/2789