Zobrazeno 1 - 10
of 88
pro vyhledávání: '"Lochet, William"'
Autor:
Aboulker, Pierre, Havet, Frédéric, Lochet, William, Lopes, Raul, Picasarri-Arrieta, Lucas, Rambaud, Clément
A class of acyclic digraphs $\mathscr{C}$ is linearly unavoidable if there exists a constant $c$ such that every digraph $D\in \mathscr{C}$ is contained in all tournaments of order $c\cdot |V(D)|$. The class of all acyclic digraphs is not linearly av
Externí odkaz:
http://arxiv.org/abs/2410.23566
Autor:
Bentert, Matthias, Fomin, Fedor V., Golovach, Petr A., Korhonen, Tuukka, Lochet, William, Panolan, Fahad, Ramanujan, M. S., Saurabh, Saket, Simonov, Kirill
Cycle packing is a fundamental problem in optimization, graph theory, and algorithms. Motivated by recent advancements in finding vertex-disjoint paths between a specified set of vertices that either minimize the total length of the paths [Bj\"orklun
Externí odkaz:
http://arxiv.org/abs/2410.18878
In the Euclidean Bottleneck Steiner Tree problem, the input consists of a set of $n$ points in $\mathbb{R}^2$ called terminals and a parameter $k$, and the goal is to compute a Steiner tree that spans all the terminals and contains at most $k$ points
Externí odkaz:
http://arxiv.org/abs/2312.01589
We revisit a natural variant of geometric set cover, called minimum-membership geometric set cover (MMGSC). In this problem, the input consists of a set $S$ of points and a set $\mathcal{R}$ of geometric objects, and the goal is to find a subset $\ma
Externí odkaz:
http://arxiv.org/abs/2305.03985
Clustering with capacity constraints is a fundamental problem that attracted significant attention throughout the years. In this paper, we give the first FPT constant-factor approximation algorithm for the problem of clustering points in a general me
Externí odkaz:
http://arxiv.org/abs/2303.07923
Publikováno v:
Electronic Journal of Combinatorics, 30/4:P4.12, 2023
We prove that every $n$-vertex $K_t$-minor-free graph $G$ of maximum degree $\Delta$ has a set $F$ of $O(t^2(\log t)^{1/4}\sqrt{\Delta n})$ edges such that every component of $G - F$ has at most $n/2$ vertices. This is best possible up to the depende
Externí odkaz:
http://arxiv.org/abs/2212.10998
Autor:
Fomin, Fedor V., Golovach, Petr A., Lochet, William, Sagunov, Danil, Simonov, Kirill, Saurabh, Saket
We study two "above guarantee" versions of the classical Longest Path problem on undirected and directed graphs and obtain the following results. In the first variant of Longest Path that we study, called Longest Detour, the task is to decide whether
Externí odkaz:
http://arxiv.org/abs/2201.03318
Autor:
Bandyapadhyay, Sayan, Fomin, Fedor V., Golovach, Petr A., Lochet, William, Purohit, Nidhi, Simonov, Kirill
$k$-means and $k$-median clustering are powerful unsupervised machine learning techniques. However, due to complicated dependences on all the features, it is challenging to interpret the resulting cluster assignments. Moshkovitz, Dasgupta, Rashtchian
Externí odkaz:
http://arxiv.org/abs/2112.06580
We design the first subexponential-time (parameterized) algorithms for several cut and cycle-hitting problems on $H$-minor free graphs. In particular, we obtain the following results (where $k$ is the solution-size parameter). 1. $2^{O(\sqrt{k}\log k
Externí odkaz:
http://arxiv.org/abs/2111.14196
Autor:
Eiben, Eduard, Fomin, Fedor V., Golovach, Petr A., Lochet, William, Panolan, Fahad, Simonov, Kirill
We consider a generalization of the fundamental $k$-means clustering for data with incomplete or corrupted entries. When data objects are represented by points in $\mathbb{R}^d$, a data point is said to be incomplete when some of its entries are miss
Externí odkaz:
http://arxiv.org/abs/2010.09580