Résumé

Counting the number of solutions of K DMDGP instances

Média

Voir la vidéo

Métriques

54
4
459.88 Ko
 application/pdf
bitcache://98e3efde0f46787bba43b71523de1a3374dbffcb

Licence

Creative Commons Aucune (Tous droits réservés)

Sponsors

Sponsors scientifique

logo_smf_cmjn.gif

Sponsors financier

logo_gdr-mia.png
logo_inria.png
image010.png
logothales.jpg

Sponsors logistique

logo-minesparistech.jpg
logo-universite-paris-sud.jpg
logo_supelec.png
Séminaire Léon Brillouin Logo
logo_cnrs_2.jpg
logo_ircam.png
logo_imb.png
<resource  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
                xmlns="http://datacite.org/schema/kernel-4"
                xsi:schemaLocation="http://datacite.org/schema/kernel-4 http://schema.datacite.org/meta/kernel-4/metadata.xsd">
        <identifier identifierType="DOI">10.23723/2552/4908</identifier><creators><creator><creatorName>Carlile Lavor</creatorName></creator><creator><creatorName>Leo Liberti</creatorName></creator><creator><creatorName>Jorge Alencar</creatorName></creator><creator><creatorName>Germano Abud</creatorName></creator></creators><titles>
            <title>Counting the number of solutions of K DMDGP instances</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2013</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><dates>
	    <date dateType="Created">Tue 17 Sep 2013</date>
	    <date dateType="Updated">Sun 25 Dec 2016</date>
            <date dateType="Submitted">Fri 20 Apr 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">98e3efde0f46787bba43b71523de1a3374dbffcb</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>25061</version>
        <descriptions>
            <description descriptionType="Abstract"></description>
        </descriptions>
    </resource>
.

Introduction The Main Result Counting the number of solutions of K DMDGP instances Leo Liberti1,2, Carlile Lavor3, Jorge Alencar3, Germano Abud3 1IBM “T.J. Watson” Research Center, Yorktown Heights, 10598 NY, USA 2LIX, Ecole Polytechnique, 91128 Palaiseau, France 3Dept. of Applied Math. , University of Campinas, Campinas – SP, Brazil Introduction The Main Result Contents 1 Introduction Distance Geometry Problem (DGP) Discretizable Molecular DGP (DMDGP) Incongruence Probability 1 Partial Reflections 2 The Main Result Counting Incongruent Realizations Introduction The Main Result Distance Geometry Problem (DGP) Discretizable Molecular DGP (DMDGP) Incongruence Probability 1 Partial Reflections Distance Geometry Problem (DGP) Given an integer K > 0 and an undirected simple graph G = (V , E), whose edges are weighted by d : E → R+, is there a function x : V → RK such that x(u) − x(v) = d({u, v}), ∀{u, v} ∈ E? In other words: find an embedding (or a realization) of G in RK , such that the Euclidean distances in RK match the given edge weights. NP-complete, for K = 1. Strongly NP-hard, for K > 1. Important case: K = 3. Introduction The Main Result Distance Geometry Problem (DGP) Discretizable Molecular DGP (DMDGP) Incongruence Probability 1 Partial Reflections Discretizable Molecular DGP (DMDGP) Given an undirected simple graph G = (V , E), whose edges are weighted by d : E → R+, and such that there is there is an order v1, v2, . . . , vn of V satisfying (a) ∀i ∈ {4, . . . , n}, ∀j, k ∈ {i − 3, . . . , i} : {vj , vk} ∈ E (b) ∀i ∈ {2, . . . , n − 1}, d(vi−1, vi+1) < d(vi−1, vi ) + d(vi , vi+1), is there an embedding x : V → R3 such that x(u) − x(v) = d({u, v}), ∀{u, v} ∈ E? Introduction The Main Result Distance Geometry Problem (DGP) Discretizable Molecular DGP (DMDGP) Incongruence Probability 1 Partial Reflections For each vertex vi (with i ≥ 4), if we know the realizations of its 3 immediate predecessors, as well as their distances to vi , then there are, with probability 1, two possible positions for vi . S2 (i − 3, di−3,i ) ∩ S2 (i − 2, di−2,i ) i − 3 i − 2 i i − 1 di−3,i−2 di−2,i−1 θi−3,i−1 i di−3,i di−3,i θi−2,i Introduction The Main Result Distance Geometry Problem (DGP) Discretizable Molecular DGP (DMDGP) Incongruence Probability 1 Partial Reflections Let ED = {{v, v − j} : j ∈ {1, . . . , K}}, EP = E \ ED and m = |E|. A discrete search is possible (Branch-and-Prune). Let X the set of all realizations. Our goal is to determine the cardinality of X. Introduction The Main Result Distance Geometry Problem (DGP) Discretizable Molecular DGP (DMDGP) Incongruence Probability 1 Partial Reflections Standard BP Introduction The Main Result Distance Geometry Problem (DGP) Discretizable Molecular DGP (DMDGP) Incongruence Probability 1 Partial Reflections Standard BP Introduction The Main Result Distance Geometry Problem (DGP) Discretizable Molecular DGP (DMDGP) Incongruence Probability 1 Partial Reflections Standard BP Introduction The Main Result Distance Geometry Problem (DGP) Discretizable Molecular DGP (DMDGP) Incongruence Probability 1 Partial Reflections Standard BP Introduction The Main Result Distance Geometry Problem (DGP) Discretizable Molecular DGP (DMDGP) Incongruence Probability 1 Partial Reflections Standard BP Introduction The Main Result Distance Geometry Problem (DGP) Discretizable Molecular DGP (DMDGP) Incongruence Probability 1 Partial Reflections Standard BP Introduction The Main Result Distance Geometry Problem (DGP) Discretizable Molecular DGP (DMDGP) Incongruence Probability 1 Partial Reflections Standard BP Introduction The Main Result Distance Geometry Problem (DGP) Discretizable Molecular DGP (DMDGP) Incongruence Probability 1 Partial Reflections Standard BP Introduction The Main Result Distance Geometry Problem (DGP) Discretizable Molecular DGP (DMDGP) Incongruence Probability 1 Partial Reflections Standard BP Introduction The Main Result Distance Geometry Problem (DGP) Discretizable Molecular DGP (DMDGP) Incongruence Probability 1 Partial Reflections Standard BP Introduction The Main Result Distance Geometry Problem (DGP) Discretizable Molecular DGP (DMDGP) Incongruence Probability 1 Partial Reflections Standard BP Introduction The Main Result Distance Geometry Problem (DGP) Discretizable Molecular DGP (DMDGP) Incongruence Probability 1 Partial Reflections Standard BP Introduction The Main Result Distance Geometry Problem (DGP) Discretizable Molecular DGP (DMDGP) Incongruence Probability 1 Partial Reflections Standard BP Introduction The Main Result Distance Geometry Problem (DGP) Discretizable Molecular DGP (DMDGP) Incongruence Probability 1 Partial Reflections Standard BP Introduction The Main Result Distance Geometry Problem (DGP) Discretizable Molecular DGP (DMDGP) Incongruence Probability 1 Partial Reflections Standard BP Introduction The Main Result Distance Geometry Problem (DGP) Discretizable Molecular DGP (DMDGP) Incongruence Probability 1 Partial Reflections Standard BP Introduction The Main Result Distance Geometry Problem (DGP) Discretizable Molecular DGP (DMDGP) Incongruence Probability 1 Partial Reflections Incongruence Two sets in RK are congruent if there is a sequence of translations, rotations and reflections that turns one into the other. X is partially correct in this respect: there is a “four level symmetry” . Half of the realizations in X are reflections of the other, along the plane through the first K vertices. Introduction The Main Result Distance Geometry Problem (DGP) Discretizable Molecular DGP (DMDGP) Incongruence Probability 1 Partial Reflections Probability 1 The theory supporting BP algorithm is based on d satisfying strict simplex inequalities. Intersection of K spheres in RK might have uncountable cardinality, or be a singleton set. We have manifolds of Lebesgue measure zero in RK . The probability of uniformly sampling d such that it yields a YES K DMDGP instance satisfying the strict simplex inequalities is 1. We state most of our results “with probability 1”. Introduction The Main Result Distance Geometry Problem (DGP) Discretizable Molecular DGP (DMDGP) Incongruence Probability 1 Partial Reflections Partial Reflections For x ∈ X and K < v ∈ V let Rv x be the reflection along the hyperplane through xv−K , . . . , xv−1. The partial reflection operator with respect to x is: gv (x) = (x1, . . . , xv−1, Rv x (xv ), Rv x (xv+1), . . . , Rv x (xn)). Figure: The action of the reflection Rv x in RK . Introduction The Main Result Distance Geometry Problem (DGP) Discretizable Molecular DGP (DMDGP) Incongruence Probability 1 Partial Reflections Partial Reflections For v > u > K and x ∈ X, we define a product between partial reflections: gugv (x) = gu(gv (x)) = gu(x1, . . . , xv?1, Rv x (xv ), . . . , Rv x (xn)) = = (x1, . . . , xu−1, Ru x (xu), . . . , Ru x (xv−1), Ru gv (x)(xv ), . . . , Ru gv (x)(xn)). Let ΓD = {gv : v > K} and GD = ΓD the invariant group of the set of realizations XD (found by the BP) of GD = (V , ED). Introduction The Main Result Distance Geometry Problem (DGP) Discretizable Molecular DGP (DMDGP) Incongruence Probability 1 Partial Reflections Assuming EP = ∅ Let {u, w} ∈ EP and define Suw = {u + K + 1, . . . , w} (u < w). GP is the subgroup of GD generated by ΓP = {gv : v > K ∧ ∀{u, w} ∈ EP(v /∈ Suw )}. 5 1 2 3 4 3 1 45 2 Figure: On the left: the set XD. On the right: the effect of the pruning edge {1, 4} on XD. Introduction The Main Result Counting Incongruent Realizations Counting Incongruent Realizations There is a integer such that |X| = 2 with probability 1. We can easily refine this: Proposition With probability 1, |X| = 2ΓP . Proof. GD ∼= Cn−K 2 , so that |GD = 2n−K |. Since GP GD, |GP| divides GD. But |GP| = 2|ΓP |. The action of GP on X has only one orbit: GPx = X, ∀x ∈ X. Every partial reflection operator is idempotent. Thus, gx = g x implies g g = 1 whence g = g and |GPx| = |GP|. For any x ∈ X, |X| = |GPx| = |GP| = 2|ΓP |. Introduction The Main Result Counting Incongruent Realizations Thank you !