Zobrazeno 1 - 10
of 938
pro vyhledávání: '"68W25"'
Autor:
Aksenov, Vitalii, Eigel, Martin
The possibility of using the Eulerian discretization for the problem of modelling high-dimensional distributions and sampling, is studied. The problem is posed as a minimization problem over the space of probability measures with respect to the Wasse
Externí odkaz:
http://arxiv.org/abs/2411.12430
Autor:
Efthymiou, Charilaos
This work establishes novel, optimum mixing bounds for the Glauber dynamics on the Hard-core and Ising models using the powerful Spectral Independence method from [Anari, Liu, Oveis-Gharan: FOCS 2020]. These bounds are expressed in terms of the local
Externí odkaz:
http://arxiv.org/abs/2411.08179
We consider two classic problems: maximum coverage and monotone submodular maximization subject to a cardinality constraint. [Nemhauser--Wolsey--Fisher '78] proved that the greedy algorithm provides an approximation of $1-1/e$ for both problems, and
Externí odkaz:
http://arxiv.org/abs/2411.05553
We consider minimum time multicasting problems in directed and undirected graphs: given a root node and a subset of $t$ terminal nodes, multicasting seeks to find the minimum number of rounds within which all terminals can be informed with a message
Externí odkaz:
http://arxiv.org/abs/2410.01048
Autor:
Bonnet, Édouard, Rzążewski, Paweł
We present a 1.8334-approximation algorithm for Vertex Cover on string graphs given with a representation, which takes polynomial time in the size of the representation; the exact approximation factor is $11/6$. Recently, the barrier of 2 was broken
Externí odkaz:
http://arxiv.org/abs/2409.18820
Autor:
Auricchio, Gennaro, Zhang, Jie
In this paper, we introduce and study the Facility Location Problem with Aleatory Agents (FLPAA), where the facility accommodates n agents larger than the number of agents reporting their preferences, namely n_r. The spare capacity is used by n_u=n-n
Externí odkaz:
http://arxiv.org/abs/2409.18817
This paper introduces the Stable Matching Based Pairing (SMBP) algorithm, a high-performance external validity index for clustering evaluation in large-scale datasets with a large number of clusters. SMBP leverages the stable matching framework to pa
Externí odkaz:
http://arxiv.org/abs/2409.14455
Autor:
Culus, Jean-François, Toulouse, Sophie
Traditionally, inapproximability results for $\mathsf{Max\,k\,CSP\!-\!q}$ have been established using balanced $t$-wise independent distributions, which are related to orthogonal arrays of strength $t$. We contribute to the field by exploring such co
Externí odkaz:
http://arxiv.org/abs/2409.03903
The $2$-Edge Connected Spanning Subgraph problem (2ECSS) is among the most basic survivable network design problems: given an undirected unweighted graph, find a subgraph with the minimum number of edges which is 2-edge-connected (i.e., it remains co
Externí odkaz:
http://arxiv.org/abs/2408.07019
We demonstrate that a wide array of machine learning algorithms are specific instances of one single paradigm: reciprocal learning. These instances range from active learning over multi-armed bandits to self-training. We show that all these algorithm
Externí odkaz:
http://arxiv.org/abs/2408.06257