TY  - JOUR
A1  - Mazzonetto, Sara
A1  - Salimova, Diyora
T1  - Existence, uniqueness, and numerical approximations for stochastic burgers equations
JF  - Stochastic analysis and applications
N2  - In this article, we propose an all-in-one statement which includes existence, uniqueness, regularity, and numerical approximations of mild solutions for a class of stochastic partial differential equations (SPDEs) with non-globally monotone nonlinearities. The proof of this result exploits the properties of an existing fully explicit space-time discrete approximation scheme, in particular the fact that it satisfies suitable a priori estimates. We also obtain almost sure and strong convergence of the approximation scheme to the mild solutions of the considered SPDEs. We conclude by applying the main result of the article to the stochastic Burgers equations with additive space-time white noise.
KW  - Stochastic Burgers equations
KW  - SPDEs
KW  - mild solution
KW  - existence
KW  - numerical
KW  - approximation
Y1  - 2020
U6  - https://doi.org/10.1080/07362994.2019.1709503
SN  - 0736-2994
SN  - 1532-9356
VL  - 38
IS  - 4
SP  - 623
EP  - 646
PB  - Taylor & Francis Group
CY  - Philadelphia
ER  - 
TY  - JOUR
A1  - Chauhan, Ankit
A1  - Friedrich, Tobias
A1  - Rothenberger, Ralf
T1  - Greed is good for deterministic scale-free networks
JF  - Algorithmica : an international journal in computer science
N2  - Large real-world networks typically follow a power-law degree distribution. To study such networks, numerous random graph models have been proposed. However, real-world networks are not drawn at random. Therefore, Brach et al. (27th symposium on discrete algorithms (SODA), pp 1306-1325, 2016) introduced two natural deterministic conditions: (1) a power-law upper bound on the degree distribution (PLB-U) and (2) power-law neighborhoods, that is, the degree distribution of neighbors of each vertex is also upper bounded by a power law (PLB-N). They showed that many real-world networks satisfy both properties and exploit them to design faster algorithms for a number of classical graph problems. We complement their work by showing that some well-studied random graph models exhibit both of the mentioned PLB properties. PLB-U and PLB-N hold with high probability for Chung-Lu Random Graphs and Geometric Inhomogeneous Random Graphs and almost surely for Hyperbolic Random Graphs. As a consequence, all results of Brach et al. also hold with high probability or almost surely for those random graph classes. In the second part we study three classical NP-hard optimization problems on PLB networks. It is known that on general graphs with maximum degree Delta, a greedy algorithm, which chooses nodes in the order of their degree, only achieves a Omega (ln Delta)-approximation forMinimum Vertex Cover and Minimum Dominating Set, and a Omega(Delta)-approximation forMaximum Independent Set. We prove that the PLB-U property with beta>2 suffices for the greedy approach to achieve a constant-factor approximation for all three problems. We also show that these problems are APX-hard even if PLB-U, PLB-N, and an additional power-law lower bound on the degree distribution hold. Hence, a PTAS cannot be expected unless P = NP. Furthermore, we prove that all three problems are in MAX SNP if the PLB-U property holds.
KW  - random graphs
KW  - deterministic properties
KW  - power-law
KW  - approximation
KW  - APX-hardness
Y1  - 2020
U6  - https://doi.org/10.1007/s00453-020-00729-z
SN  - 0178-4617
SN  - 1432-0541
VL  - 82
IS  - 11
SP  - 3338
EP  - 3389
PB  - Springer
CY  - New York
ER  -