Refine my results

Language

Università della Svizzera italiana

Hard and soft EM in bayesian network learning from incomplete data

Ruggieri, Andrea ; Stranieri, Francesco ; Stella, Fabio ; Scutari, Marco

In: Algorithms, 2020, vol. 13, no. 12, p. 17

Incomplete data are a common feature in many domains, from clinical trials to industrial applications. Bayesian networks (BNs) are often used in these domains because of their graphical and causal interpretations. BN parameter learning from incomplete data is usually implemented with the Expectation-Maximisation algorithm (EM), which computes the relevant sufficient statistics (“soft EM”) ...

Université de Fribourg

CPG graphs : Some Structural and Hardness Results

Champseix, Nicolas ; Galby, Esther ; Munaro, Andrea ; Ries, Bernard

In: Discrete Applied Mathematics, 2021, vol. 290, p. 17-35

In this paper we continue the systematic study of Contact graphs of Paths on a Grid (CPG graphs) initiated in Deniz et al. (2018). A CPG graph is a graph for which there exists a collection of pairwise interiorly disjoint paths on a grid in one-to-one correspondence with its vertex set such that two vertices are adjacent if and only if the corresponding paths touch at a grid-point. If every...

Università della Svizzera italiana

Approximation algorithms for survivable network design

Jabal Ameli, Afrouz ; Grandoni, Fabrizio (Dir.)

Thèse de doctorat : Università della Svizzera italiana, 2021 ; 2021INFO005.

Many relevant discrete optimization problems are believed to be hard to solve efficiently (i.e. they cannot be solved in polynomial time unless P=NP). An approximation algorithm is one of the ways to tackle these hard optimization problems. These algorithms have polynomial running time and compute a feasible solution whose value is within a proven factor (approximation factor) of the optimal...

Università della Svizzera italiana

Advanced metaheuristics for the probabilistic orienteering problem

Chou, Xiaochen ; Gambardella, Luca Maria (Dir.) ; Montemanni, Roberto (Codir.)

Thèse de doctorat : Università della Svizzera italiana, 2020 ; 2020INFO020.

Stochastic Optimization Problems take uncertainty into account. For this reason they are in general more realistic than deterministic ones, meanwhile, more difficult to solve. The challenge is both on modelling and computation aspects: exact methods usually work only for small instances, besides, there are several problems with no closed-form expression or hard- to-compute objective functions....

Université de Fribourg

Reducing the domination number of graphs via edge contractions and vertex deletions

Galby, Esther ; Lima, Paloma T. ; Ries, Bernard

In: Discrete Mathematics, 2021, vol. 344, no. 1, p. 112169

In this work, we study the following problem: given a connected graph G, can we reduce the domination number of G by at least one using k edge contractions, for some fixed integer k > 0? We show that for k = 1 (resp. k = 2), the problem is NP-hard (resp. coNP-hard). We further prove that for k = 1, the problem is W[1]-hard parameterized by domination number plus the mim-width of the input...

Université de Fribourg

Complexity and Algorithms for Finding a Perfect Phylogeny from Mixed Tumor Samples

Hujdurovic, Ademir ; Kacar, Ursula ; Milanic, Martin ; Ries, Bernard ; Tomescu, Alexandru I.

In: IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2018, vol. 15, no. 1, p. 96-108

Hajirasouliha and Raphael (WABI 2014) proposed a model for deconvoluting mixed tumor samples measured from a collection of high-throughput sequencing reads. This is related to understanding tumor evolution and critical cancer mutations. In short, their formulation asks to split each row of a binary matrix so that the resulting matrix corresponds to a perfect phylogeny and has the minimum...

Université de Fribourg

Semitotal Domination: New hardness results and a polynomial-time algorithm for graphs of bounded mim-width

Galby, Esther ; Munaro, Andrea ; Ries, Bernard

In: Theoretical Computer Science, 2020, vol. 814, p. 28-48

A semitotal dominating set of a graph G with no isolated vertex is a dominating set D of G such that every vertex in D is within distance two of another vertex in D. The minimum size γt2(G) of a semitotal dominating set of G is squeezed between the domination number γ(G) and the total domination number γt(G). Semitotal Dominating Set is the problem of finding, given a graph G, a semitotal...