The Experts below are selected from a list of 8913 Experts worldwide ranked by ideXlab platform

Nayyeri Amir - One of the best experts on this subject based on the ideXlab platform.

  • Minimum Bounded Chains and Minimum Homologous Chains in Embedded Simplicial Complexes
    LIPIcs - Leibniz International Proceedings in Informatics. 36th International Symposium on Computational Geometry (SoCG 2020), 2020
    Co-Authors: Borradaile Glencora, Maxwell William, Nayyeri Amir
    Abstract:

    We study two optimization problems on simplicial complexes with homology over ??, the minimum Bounded Chain problem: given a d-dimensional complex ? embedded in ?^(d+1) and a null-homologous (d-1)-cycle C in ?, find the minimum d-Chain with boundary C, and the minimum homologous Chain problem: given a (d+1)-manifold ? and a d-Chain D in ?, find the minimum d-Chain homologous to D. We show strong hardness results for both problems even for small values of d; d = 2 for the former problem, and d=1 for the latter problem. We show that both problems are APX-hard, and hard to approximate within any constant factor assuming the unique games conjecture. On the positive side, we show that both problems are fixed-parameter tractable with respect to the size of the optimal solution. Moreover, we provide an O(?{log ?_d})-approximation algorithm for the minimum Bounded Chain problem where ?_d is the dth Betti number of ?. Finally, we provide an O(?{log n_{d+1}})-approximation algorithm for the minimum homologous Chain problem where n_{d+1} is the number of (d+1)-simplices in ?

  • Minimum Bounded Chains and minimum homologous Chains in embedded simplicial complexes
    2020
    Co-Authors: Borradaile Glencora, Maxwell William, Nayyeri Amir
    Abstract:

    We study two optimization problems on simplicial complexes with homology over $\mathbb{Z}_2$, the minimum Bounded Chain problem: given a $d$-dimensional complex $\mathcal{K}$ embedded in $\mathbb{R}^{d+1}$ and a null-homologous $(d-1)$-cycle $C$ in $\mathcal{K}$, find the minimum $d$-Chain with boundary $C$, and the minimum homologous Chain problem: given a $(d+1)$-manifold $\mathcal{M}$ and a $d$-Chain $D$ in $\mathcal{M}$, find the minimum $d$-Chain homologous to $D$. We show strong hardness results for both problems even for small values of $d$; $d = 2$ for the former problem, and $d=1$ for the latter problem. We show that both problems are APX-hard, and hard to approximate within any constant factor assuming the unique games conjecture. On the positive side, we show that both problems are fixed parameter tractable with respect to the size of the optimal solution. Moreover, we provide an $O(\sqrt{\log \beta_d})$-approximation algorithm for the minimum Bounded Chain problem where $\beta_d$ is the $d$th Betti number of $\mathcal{K}$. Finally, we provide an $O(\sqrt{\log n_{d+1}})$-approximation algorithm for the minimum homologous Chain problem where $n_{d+1}$ is the number of $d$-simplices in $\mathcal{M}$

Borradaile Glencora - One of the best experts on this subject based on the ideXlab platform.

  • Minimum Bounded Chains and Minimum Homologous Chains in Embedded Simplicial Complexes
    LIPIcs - Leibniz International Proceedings in Informatics. 36th International Symposium on Computational Geometry (SoCG 2020), 2020
    Co-Authors: Borradaile Glencora, Maxwell William, Nayyeri Amir
    Abstract:

    We study two optimization problems on simplicial complexes with homology over ??, the minimum Bounded Chain problem: given a d-dimensional complex ? embedded in ?^(d+1) and a null-homologous (d-1)-cycle C in ?, find the minimum d-Chain with boundary C, and the minimum homologous Chain problem: given a (d+1)-manifold ? and a d-Chain D in ?, find the minimum d-Chain homologous to D. We show strong hardness results for both problems even for small values of d; d = 2 for the former problem, and d=1 for the latter problem. We show that both problems are APX-hard, and hard to approximate within any constant factor assuming the unique games conjecture. On the positive side, we show that both problems are fixed-parameter tractable with respect to the size of the optimal solution. Moreover, we provide an O(?{log ?_d})-approximation algorithm for the minimum Bounded Chain problem where ?_d is the dth Betti number of ?. Finally, we provide an O(?{log n_{d+1}})-approximation algorithm for the minimum homologous Chain problem where n_{d+1} is the number of (d+1)-simplices in ?

  • Minimum Bounded Chains and minimum homologous Chains in embedded simplicial complexes
    2020
    Co-Authors: Borradaile Glencora, Maxwell William, Nayyeri Amir
    Abstract:

    We study two optimization problems on simplicial complexes with homology over $\mathbb{Z}_2$, the minimum Bounded Chain problem: given a $d$-dimensional complex $\mathcal{K}$ embedded in $\mathbb{R}^{d+1}$ and a null-homologous $(d-1)$-cycle $C$ in $\mathcal{K}$, find the minimum $d$-Chain with boundary $C$, and the minimum homologous Chain problem: given a $(d+1)$-manifold $\mathcal{M}$ and a $d$-Chain $D$ in $\mathcal{M}$, find the minimum $d$-Chain homologous to $D$. We show strong hardness results for both problems even for small values of $d$; $d = 2$ for the former problem, and $d=1$ for the latter problem. We show that both problems are APX-hard, and hard to approximate within any constant factor assuming the unique games conjecture. On the positive side, we show that both problems are fixed parameter tractable with respect to the size of the optimal solution. Moreover, we provide an $O(\sqrt{\log \beta_d})$-approximation algorithm for the minimum Bounded Chain problem where $\beta_d$ is the $d$th Betti number of $\mathcal{K}$. Finally, we provide an $O(\sqrt{\log n_{d+1}})$-approximation algorithm for the minimum homologous Chain problem where $n_{d+1}$ is the number of $d$-simplices in $\mathcal{M}$

Maxwell William - One of the best experts on this subject based on the ideXlab platform.

  • Minimum Bounded Chains and Minimum Homologous Chains in Embedded Simplicial Complexes
    LIPIcs - Leibniz International Proceedings in Informatics. 36th International Symposium on Computational Geometry (SoCG 2020), 2020
    Co-Authors: Borradaile Glencora, Maxwell William, Nayyeri Amir
    Abstract:

    We study two optimization problems on simplicial complexes with homology over ??, the minimum Bounded Chain problem: given a d-dimensional complex ? embedded in ?^(d+1) and a null-homologous (d-1)-cycle C in ?, find the minimum d-Chain with boundary C, and the minimum homologous Chain problem: given a (d+1)-manifold ? and a d-Chain D in ?, find the minimum d-Chain homologous to D. We show strong hardness results for both problems even for small values of d; d = 2 for the former problem, and d=1 for the latter problem. We show that both problems are APX-hard, and hard to approximate within any constant factor assuming the unique games conjecture. On the positive side, we show that both problems are fixed-parameter tractable with respect to the size of the optimal solution. Moreover, we provide an O(?{log ?_d})-approximation algorithm for the minimum Bounded Chain problem where ?_d is the dth Betti number of ?. Finally, we provide an O(?{log n_{d+1}})-approximation algorithm for the minimum homologous Chain problem where n_{d+1} is the number of (d+1)-simplices in ?

  • Minimum Bounded Chains and minimum homologous Chains in embedded simplicial complexes
    2020
    Co-Authors: Borradaile Glencora, Maxwell William, Nayyeri Amir
    Abstract:

    We study two optimization problems on simplicial complexes with homology over $\mathbb{Z}_2$, the minimum Bounded Chain problem: given a $d$-dimensional complex $\mathcal{K}$ embedded in $\mathbb{R}^{d+1}$ and a null-homologous $(d-1)$-cycle $C$ in $\mathcal{K}$, find the minimum $d$-Chain with boundary $C$, and the minimum homologous Chain problem: given a $(d+1)$-manifold $\mathcal{M}$ and a $d$-Chain $D$ in $\mathcal{M}$, find the minimum $d$-Chain homologous to $D$. We show strong hardness results for both problems even for small values of $d$; $d = 2$ for the former problem, and $d=1$ for the latter problem. We show that both problems are APX-hard, and hard to approximate within any constant factor assuming the unique games conjecture. On the positive side, we show that both problems are fixed parameter tractable with respect to the size of the optimal solution. Moreover, we provide an $O(\sqrt{\log \beta_d})$-approximation algorithm for the minimum Bounded Chain problem where $\beta_d$ is the $d$th Betti number of $\mathcal{K}$. Finally, we provide an $O(\sqrt{\log n_{d+1}})$-approximation algorithm for the minimum homologous Chain problem where $n_{d+1}$ is the number of $d$-simplices in $\mathcal{M}$

Bruno Teheux - One of the best experts on this subject based on the ideXlab platform.

  • Generalized Sugeno Integrals
    2016
    Co-Authors: Didier Dubois, Henri Prade, Agnés Rico, Bruno Teheux
    Abstract:

    Sugeno integrals are aggregation functions defined on a qualitative scale where only minimum, maximum and order-reversing maps are allowed. Recently, variants of Sugeno integrals based on Gödel implication and its contraposition were defined and axiomatized in the setting of Bounded Chain with an involutive negation. This paper proposes a more general approach. We consider totally ordered scales, multivalued conjunction operations not necessarily commutative, and implication operations induced from them by means of an involutive negation. In such a context, different Sugeno-like integrals are defined and axiomatized.

Teheux Bruno - One of the best experts on this subject based on the ideXlab platform.

  • Generalized Sugeno Integrals
    HAL CCSD, 2016
    Co-Authors: Dubois Didier, Prade Henri, Rico Agnés, Teheux Bruno
    Abstract:

    International audienceSugeno integrals are aggregation functions defined on a qualitative scale where only minimum, maximum and order-reversing maps are allowed. Recently, variants of Sugeno integrals based on Gödel implication and its contraposition were defined and axiomatized in the setting of Bounded Chain with an involutive negation. This paper proposes a more general approach. We consider totally ordered scales, multivalued conjunction operations not necessarily commutative, and implication operations induced from them by means of an involutive negation. In such a context, different Sugeno-like integrals are defined and axiomatized