All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 7 Next

Displaying 121 – 140 of 156

Showing per page

An improved derandomized approximation algorithm for the max-controlled set problem

Carlos Martinhon, Fábio Protti (2011)

RAIRO - Theoretical Informatics and Applications

A vertex i of a graph G = (V,E) is said to be controlled by M ⊆ V if the majority of the elements of the neighborhood of i (including itself) belong to M. The set M is a monopoly in G if every vertex i ∈ V is controlled by M. Given a set M ⊆ V and two graphs G1 = ( V , E 1 ) and G2 = ( V , E 2 ) where E 1 ⊆ E 2 , the monopoly verification problem (mvp) consists of deciding whether there exists a sandwich graph G = (V,E) (i.e., a graph where E 1 ⊆ E ⊆ E 2 ) such that M is a monopoly in G = (V,E). If the answer to the mvp is No, we then consider...

An intrinsically non minimal-time Minsky-like 6-states solution to the Firing Squad synchronization problem

Jean-Baptiste Yunès (2008)

RAIRO - Theoretical Informatics and Applications

Here is presented a 6-states non minimal-time solution which is intrinsically Minsky-like and solves the three following problems: unrestricted version on a line, with one initiator at each end of a line and the problem on a ring. We also give a complete proof of correctness of our solution, which was never done in a publication for Minsky's solutions.

An introduction to quantum annealing

Diego de Falco, Dario Tamascelli (2011)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Quantum annealing, or quantum stochastic optimization, is a classical randomized algorithm which provides good heuristics for the solution of hard optimization problems. The algorithm, suggested by the behaviour of quantum systems, is an example of proficuous cross contamination between classical and quantum computer science. In this survey paper we illustrate how hard combinatorial problems are tackled by quantum computation and present some examples of the heuristics provided by quantum annealing....

An introduction to quantum annealing

Diego de Falco, Dario Tamascelli (2011)

RAIRO - Theoretical Informatics and Applications

Quantum annealing, or quantum stochastic optimization, is a classical randomized algorithm which provides good heuristics for the solution of hard optimization problems. The algorithm, suggested by the behaviour of quantum systems, is an example of proficuous cross contamination between classical and quantum computer science. In this survey paper we illustrate how hard combinatorial problems are tackled by quantum computation and present some examples of the heuristics provided by quantum annealing....

Analysis of a near-metric TSP approximation algorithm

Sacha Krug (2013)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

The traveling salesman problem (TSP) is one of the most fundamental optimization problems. We consider the β-metric traveling salesman problem (Δβ-TSP), i.e., the TSP restricted to graphs satisfying the β-triangle inequality c({v,w}) ≤ β(c({v,u}) + c({u,w})), for some cost function c and any three vertices u,v,w. The well-known path matching Christofides algorithm (PMCA) guarantees an approximation ratio of 3β2/2 and is the best known algorithm for the Δβ-TSP, for 1 ≤ β ≤ 2. We provide a complete...

Analysis of Markov chain algorithms on spanning trees, rooted forests, and connected subgraphs

Johannes Fehrenbach, Ludger Rüschendorf (2005)

Applicationes Mathematicae

We analyse a natural edge exchange Markov chain on the set of spanning trees of an undirected graph by the method of multicommodity flows. The analysis is then refined to obtain a canonical path analysis. The construction of the flow and of the canonical paths is based on related path constructions in a paper of Cordovil and Moreira (1993) on block matroids. The estimates of the congestion measure imply a polynomial bound on the mixing time. The canonical paths for spanning trees also yield polynomial...

Approximation algorithms for metric tree cover and generalized tour and tree covers

Viet Hung Nguyen (2007)

RAIRO - Operations Research

Given a weighted undirected graph G = (V,E), a tree (respectively tour) cover of an edge-weighted graph is a set of edges which forms a tree (resp. closed walk) and covers every other edge in the graph. The tree (resp. tour) cover problem is of finding a minimum weight tree (resp. tour) cover of G. Arkin, Halldórsson and Hassin (1993) give approximation algorithms with factors respectively 3.5 and 5.5. Later Könemann, Konjevod, Parekh, and Sinha (2003) study the linear programming relaxations...

Currently displaying 121 – 140 of 156