Browsing Bergen Open Research Archive by Author "Fomin, Fedor"

Parameterization Above a Multiplicative Guarantee

Fomin, Fedor; Golovach, Petr; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket; Zehavi, Meirav (Journal article; Peer reviewed, 2020)

Parameterization above a guarantee is a successful paradigm in Parameterized Complexity. To the best of our knowledge, all fixed-parameter tractable problems in this paradigm share an additive form defined as follows. Given ...

Parameterized complexity of categorical clustering with size constraints

Fomin, Fedor; Golovach, Petr; Purohit, Nidhi (Journal article; Peer reviewed, 2023)

Parameterized Complexity of Directed Spanner Problems

Fomin, Fedor; Golovach, Petr; Lochet, William; Misra, Pranabendu; Saurabh, Saket; Sharma, Roohani (Journal article; Peer reviewed, 2020)

We initiate the parameterized complexity study of minimum t-spanner problems on directed graphs. For a positive integer t, a multiplicative t-spanner of a (directed) graph G is a spanning subgraph H such that the distance ...

Parameterized Complexity of Directed Spanner Problems

Fomin, Fedor; Golovach, Petr; Lochet, William Alexandre; Misra, Pranabendu; Saurabh, Saket; Sharma, Roohani (Journal article; Peer reviewed, 2021)

We initiate the parameterized complexity study of minimum t-spanner problems on directed graphs. For a positive integer t, a multiplicative t-spanner of a (directed) graph G is a spanning subgraph H such that the distance ...

Parameterized Complexity of Feature Selection for Categorical Data Clustering

Bandyapadhyay, Sayan; Fomin, Fedor; Golovach, Petr; Simonov, Kirill (Journal article; Peer reviewed, 2021)

We develop new algorithmic methods with provable guarantees for feature selection in regard to categorical data clustering. While feature selection is one of the most common approaches to reduce dimensionality in practice, ...

Parameterized complexity of PCA

Fomin, Fedor; Golovach, Petr; Simonov, Kirill (Journal article; Peer reviewed, 2020)

We discuss some recent progress in the study of Principal Component Analysis (PCA) from the perspective of Parameterized Complexity.

Parameterized complexity of secluded connectivity problems

Fomin, Fedor; Golovach, Petr; Karpov, Nikolay; Kulikov, Alexander S (Peer reviewed; Journal article, 2015)

The Secluded Path problem introduced by Chechik et al. in [ESA 2013] models a situation where a sensitive information has to be transmitted between a pair of nodes along a path in a network. The measure of the quality of ...

Parameterized complexity of the spanning tree congestion problem

Bodlaender, Hans L.; Fomin, Fedor; Golovach, Petr; Otachi, Yota; van Leeuwen, Erik Jan (Peer reviewed; Journal article, 2012-09)

We study the problem of determining the spanning tree congestion of a graph. We present some sharp contrasts in the parameterized complexity of this problem. First, we show that on apex-minor-free graphs, a general class ...

Parameterized k-Clustering: Tractability Island

Fomin, Fedor; Golovach, Petr; Simonov, Kirill (Peer reviewed; Journal article, 2019)

In k-Clustering we are given a multiset of n vectors X subset Z^d and a nonnegative number D, and we need to decide whether X can be partitioned into k clusters C_1, ..., C_k such that the cost sum_{i=1}^k min_{c_i in R^d} ...

Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree

Fomin, Fedor; Kaski, Petteri; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket (Peer reviewed; Journal article, 2019)

In the Steiner Tree problem, we are given as input a connected $n$-vertex graph with edge weights in $\{1,2,\ldots,W\}$, and a set of $k$ terminal vertices. Our task is to compute a minimum-weight tree that contains ...

Path contraction faster than $2^n$

Agrawal, Akanksha; Fomin, Fedor; Lokshtanov, Daniel; Saurabh, Saket; Tale, Prafullkumar (Journal article; Peer reviewed, 2020)

A graph $G$ is contractible to a graph $H$ if there is a set $X \subseteq E(G)$, such that $G/X$ is isomorphic to $H$. Here, $G/X$ is the graph obtained from $G$ by contracting all the edges in $X$. For a family of graphs ...

Path Contraction Faster Than 2n

Agrawal, Akanksha; Fomin, Fedor; Lokshtanov, Daniel; Saurabh, Saket; Tale, Prafullkumar (Peer reviewed; Journal article, 2019)

A graph G is contractible to a graph H if there is a set X subseteq E(G), such that G/X is isomorphic to H. Here, G/X is the graph obtained from G by contracting all the edges in X. For a family of graphs F, the F-Contraction ...

Present-biased optimization

Fomin, Fedor; Fraigniaud, Pierre; Golovach, Petr (Journal article; Peer reviewed, 2022)

This paper explores the behavior of present-biased agents, that is, agents who erroneously anticipate the costs of future actions compared to their real costs. Specifically, we extend the original framework proposed by ...

(Re)packing Equal Disks into Rectangle

Fomin, Fedor; Golovach, Petr; Inamdar, Tanmay Nitin; Zehavi, Meirav (Journal article; Peer reviewed, 2022)

The problem of packing of equal disks (or circles) into a rectangle is a fundamental geometric problem. (By a packing here we mean an arrangement of disks in a rectangle without overlapping.) We consider the following ...

Refined Complexity of PCA with Outliers

Fomin, Fedor; Golovach, Petr; Panolan, Fahad; Simonov, Kirill (Peer reviewed; Journal article, 2019)

Principal component analysis (PCA) is one of the most fundamental procedures in exploratory data analysis and is the basic step in applications ranging from quantitative finance and bioinformatics to image analysis and ...

Search for Higgs boson decays into a pair of light bosons in the bbμμ final state in pp collision at √s=13 TeV with the ATLAS detector

Aaboud, Morad; Aad, Georges; Abbott, Brad; Abdinov, Ovsat Bahram oglu; Abeloos, Baptiste; Abhayasinghe, Deshan Kavishka; Abidi, Syed Haider; AbouZeid, Hass; Abraham, Nadine L.; Abramowicz, Halina; Buanes, Trygve; Djuvsland, Julia Isabell; Eigen, Gerald; Fomin, Fedor; Lipniacka, Anna; Martin dit Latour, Bertrand; Mæland, Steffen; Stugu, Bjarne; Yang, Zongchang; Zalieckas, Justas; Bugge, Magnar Kopangen; Cameron, David Gordon; Catmore, James Richard; Feigl, Simon; Franconi, Laura; Garonne, Vincent; Gramstad, Eirik; Hellesund, Simen; Morisbak, Vanja; Oppen, Henrik; Ould-Saada, Farid; Pedersen, Maiken; Read, Alexander Lincoln; Røhne, Ole Myren; Sandaker, Heidi; Serfon, Cédric; Stapnes, Steinar; Vadla, Knut Oddvar Høie; Abreu, Henso; Abulaiti, Yiming; Acharya, Bobby S.; Adachi, Shunsuke; Adamczyk, Leszek; Adelman, Jareed; Adersberger, Michael; Adigüzel, Aytül; Adye, Tim; Affolder, Anthony Allen; Afik, Yoav; Agheorghiesei, Catalin; ATLAS, Collaboration (Peer reviewed; Journal article, 2019-03-10)

A search for decays of the Higgs boson into a pair of new spin-zero particles, H → aa, where the a-bosons decay into a b-quark pair and a muon pair, is presented. The search uses 36.1 fb−1 of proton–proton collision data ...