Search Limiters: Peer Reviewed / Topic: mathematics - Searchworks@Jio Institute Digital Library Search Results

Showing total 70 results

Start Over Search Limiters Peer Reviewed Topic mathematics

70 results

1. Asset Price Bubbles: Invariance Theorems*

Author: Robert Jarrow, Philip Protter, Jaime San Martin, and Johnson School Working Paper Series
Subjects: Computer Science::Computer Science and Game Theory, Frequentist probability, Stochastic volatility, Markov chain, Local martingale, Econometrics, Asset (economics), Measure (mathematics), Quadratic variation, Economic bubble, Mathematics
Abstract: This paper provides invariance theorems that facilitate testing for the existence of an asset price bubble in a market where the price evolves as a Markov diffusion process. The test involves only the properties of the price process’ quadratic variation under the statistical probability. It does not require an estimate of either the equivalent local martingale measure or the asset’s drift. To augment its use, a new family of stochastic volatility price processes is also provided where the processes’ strict local martingale behavior can be characterized.
Published: 2020

2. Predictive Modeling Through Regression

Author: David Paper
Subjects: Floating point, Variables, media_common.quotation_subject, Statistics, Value (computer science), Class (biology), Regression, Mathematics, Variable (mathematics), Integer (computer science), media_common
Abstract: While classification is the problem of predicting a discrete class label for an example, regression predictive modeling (or just regression) is the problem of learning the strength of association between independent variables (or features) and continuous dependent variables (or outcomes). A continuous output variable is a real value such as an integer or floating point value often quantified as amounts and sizes.
Published: 2019

3. Scikit-Learn Regression Tuning

Author: David Paper
Subjects: Hyperparameter, Statistics::Theory, Variables, media_common.quotation_subject, Regression, Statistics::Computation, Statistics::Machine Learning, Statistical classification, ComputingMethodologies_PATTERNRECOGNITION, Statistics, Statistics::Methodology, Regression algorithm, Association (psychology), Mathematics, media_common
Abstract: Regression predictive modeling (or just regression) is the problem of learning the strength of association between independent variables (or features) and continuous dependent variables (or outcomes). Tuning regression algorithms is similar to tuning classification algorithms. That is, we adjust a model’s hyperparameters until we arrive at an optimal solution.
Published: 2019

4. What Corporations Want

Author: McGill, Clearance, Williams, Ernie, Paper, Scott, Adams, Rudy, Wheeler, Foster, Neiger, Bob, and Davis, Ollie
Published: 1983

5. The DFT operational Sum Calculus Method for Solving Difference Equations with Boundary Conditions

Author: Abdul j. Jerri ∗ This paper is dedicated to
Subjects: Algebra and Number Theory, Applied Mathematics, Multivariable calculus, Sum rule in integration, Calculus, medicine, Time-scale calculus, Boundary value problem, medicine.disease, Analysis, Calculus (medicine), Mathematics
Published: 1997

6. Entropy and the Value of Information for Investors

Author: Brown Economics Working Paper Series, Antonio Cabrales, Olivier Gossner, and Roberto Serrano
Subjects: Entropy (classical thermodynamics), Information structure, Set (psychology), Investment (macroeconomics), Mathematical economics, Mathematics, Value of information
Abstract: Consider any investor who fears ruin facing any set of investments that satisfy no-arbitrage. Before investing, he can purchase information about the state of nature in the form of an information structure. Given his prior, information structure is more informative than information structure if whenever he rejects at some price, he also rejects at that price. We show that this complete informativeness ordering is represented by the decrease in entropy of his beliefs, regardless of his preferences, initial wealth or investment problem. It is also shown that no prior-independent informativeness ordering based on similar premises exists.
Published: 2010

7. The Symbol [heart]

Author: Herbert H. Paper
Subjects: Linguistics and Language, Symbol, Communication, media_common.quotation_subject, Arithmetic, Language and Linguistics, media_common, Mathematics
Published: 1985

8. A generic exact solver for vehicle routing and related problems

Author: Eduardo Uchoa, Artur Alves Pessoa, Ruslan Sadykov, François Vanderbeck, Universidade Federal Fluminense [Rio de Janeiro] (UFF), Reformulations based algorithms for Combinatorial Optimization (Realopt), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS), Atoptima, We would like to thank Teobaldo Bulhoes and Guillaume Marques for a large part of the implementation of the Julia–JuMP interface to the solver, Teobaldo Bulhoes, Guillaume Marques and Eduardo Queiroga for implementing, over that interface, the models corresponding to the examples of this paper, and Laurent Facq for a general support of the computing environment. Experiments presented in this paper were carried out using the PlaFRIM (Federative Platform for Research in Computer Science and Mathematics), created under the Inria PlaFRIM development action with support from Bordeaux INP, LABRI and IMB and other entities: Conseil Régional d’Aquitaine, Université de Bordeaux, CNRS and ANR in accordance to the 'Programme d’Investissements d’Avenir'. This study was financed in part by the Conselho Nacional de Científico e Tecnológico (CNPq), grant 313601/2018-6 (Produtividade 1B), and by the Funda¸c˜ao de Amparo à Pesquisa do Estado do Rio de Janeiro (FAPERJ), grant E-26/202.887/2017 (Cientista do Estado)., Plafrim, Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, and Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Mathematical optimization, 021103 operations research, Bin packing problem, General Mathematics, Column generation, 0211 other engineering and technologies, Integer programming, Rule-based system, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], 010103 numerical & computational mathematics, 02 engineering and technology, Solver, 01 natural sciences, Vehicle routing problem, Path (graph theory), 0101 mathematics, Routing (electronic design automation), Software, Routing, Mathematics
Abstract: Major advances were recently obtained in the exact solution of vehicle routing problems (VRPs). Sophisticated branch-cut-and-price (BCP) algorithms for some of the most classical VRP variants now solve many instances with up to a few hundreds of customers. However, adapting and reimplementing those successful algorithms for other variants can be a very demanding task. This work proposes a BCP solver for a generic model that encompasses a wide class of VRPs. It incorporates the key elements found in the best existing VRP algorithms: ng-path relaxation, rank-1 cuts with limited memory, path enumeration, and rounded capacity cuts; all generalized through the new concepts of “packing set” and “elementarity set”. The concepts are also used to derive a branching rule based on accumulated resource consumption and to generalize the Ryan and Foster branching rule. Extensive experiments on several variants show that the generic solver has an excellent overall performance, in many problems being better than the best specific algorithms. Even some non-VRPs, like bin packing, vector packing and generalized assignment, can be modeled and effectively solved.
Published: 2020

9. Enclosings of decompositions of complete multigraphs in 2-edge-connected r -factorizations

Author: John Asplund, Pierre Charbit, Carl Feghali, Dalton State College, University System of Georgia (USG), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Networks, Graphs and Algorithms (GANG), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), University of Bergen (UIB), This paper received partial support his paper received partial support by Fondation Sciences Mathématiques de Paris and the Research Council of Norway via the project CLASSIS, Grant Number 249994., and University of Bergen (UiB)
Subjects: Discrete mathematics, 010102 general mathematics, Multigraph, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], 01 natural sciences, Theoretical Computer Science, Combinatorics, Factorization, 010201 computation theory & mathematics, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, Discrete Mathematics and Combinatorics, Partition (number theory), Mathematics - Combinatorics, Combinatorics (math.CO), 0101 mathematics, ComputingMilieux_MISCELLANEOUS, Mathematics, 05B99
Abstract: A decomposition of a multigraph $G$ is a partition of its edges into subgraphs $G(1), \ldots , G(k)$. It is called an $r$-factorization if every $G(i)$ is $r$-regular and spanning. If $G$ is a subgraph of $H$, a decomposition of $G$ is said to be enclosed in a decomposition of $H$ if, for every $1 \leq i \leq k$, $G(i)$ is a subgraph of $H(i)$. Feghali and Johnson gave necessary and sufficient conditions for a given decomposition of $\lambda K_n$ to be enclosed in some $2$-edge-connected $r$-factorization of $\mu K_{m}$ for some range of values for the parameters $n$, $m$, $\lambda$, $\mu$, $r$: $r=2$, $\mu>\lambda$ and either $m \geq 2n-1$, or $m=2n-2$ and $\mu = 2$ and $\lambda=1$, or $n=3$ and $m=4$. We generalize their result to every $r \geq 2$ and $m \geq 2n - 2$. We also give some sufficient conditions for enclosing a given decomposition of $\lambda K_n$ in some $2$-edge-connected $r$-factorization of $\mu K_{m}$ for every $r \geq 3$ and $m = (2 - C)n$, where $C$ is a constant that depends only on $r$, $\lambda$ and~$\mu$., Comment: 17 pages; fixed the proof of Theorem 1.4 and other minor changes
Published: 2019

10. The controversial anti-Semitic journal in mathematics: the stakes are not little.

Author: Beck, Anatole and Paper, Herbert H.
Subjects: LETTERS to the editor, MATHEMATICS
Abstract: A letter to the editor is presented in response to the previous article related to anti-Semitic journal in mathematics in the January 26, 1981 issue.
Published: 1981

11. Towards a symplectic version of the Chevalley restriction theorem

Author: Ronan Terpereau, Manfred Lehn, Christian Lehn, Michael Bulois, Algèbre, géométrie, logique ( AGL ), Institut Camille Jordan [Villeurbanne] ( ICJ ), École Centrale de Lyon ( ECL ), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 ( UCBL ), Université de Lyon-Institut National des Sciences Appliquées de Lyon ( INSA Lyon ), Université de Lyon-Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Université Jean Monnet [Saint-Étienne] ( UJM ) -Centre National de la Recherche Scientifique ( CNRS ) -École Centrale de Lyon ( ECL ), Université de Lyon-Institut National des Sciences Appliquées ( INSA ) -Institut National des Sciences Appliquées ( INSA ) -Université Jean Monnet [Saint-Étienne] ( UJM ) -Centre National de la Recherche Scientifique ( CNRS ), Fakultät für Mathematik der Technischen Universität Chemnitz, Fakultaet fuer Mathematik der Technischen Universitaet Chemnitz, Institut für Mathematik ( MI ), Johannes Gutenberg - Universität Mainz ( JGU ), Institut de Mathématiques de Bourgogne [Dijon] ( IMB ), Université de Bourgogne ( UB ) -Centre National de la Recherche Scientifique ( CNRS ), Max Planck Institute for Mathematics ( Bonn ), The second-named author gratefully acknowledges the support by the DFG through the research grant Le 3093/2-1. The thirdnamed author is supported by the SFB Transregio 45 'Periods, Moduli Spaces and Arithmetic of Algebraic Varieties'. The fourth-named author is grateful to the Max-Planck-Institut für Mathematik of Bonn for the warm hospitality and support provided during the writing of this paper. Part ofthe genesis of this paper occurred during the half semester Algebraic Groups and Representations supported by the LABEX MILYON (ANR-10-LABX-0070) of Université de Lyon, within the program 'Investissements d'Avenir' (ANR-11-IDEX-0007) operated by the French National Research Agency (ANR)., ANR-11-IDEX-0007-02/10-LABX-0070,MILYON,Community of mathematics and fundamental computer science in Lyon ( 2011 ), ANR-15-CE40-0012,GeoLie,GeoLie, Algèbre, géométrie, logique (AGL), Institut Camille Jordan [Villeurbanne] (ICJ), École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Jean Monnet [Saint-Étienne] (UJM)-Centre National de la Recherche Scientifique (CNRS)-École Centrale de Lyon (ECL), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Jean Monnet [Saint-Étienne] (UJM)-Centre National de la Recherche Scientifique (CNRS), Chemnitz University of Technology / Technische Universität Chemnitz, Institut für Mathematik (MI), Johannes Gutenberg - Universität Mainz (JGU), Institut de Mathématiques de Bourgogne [Dijon] (IMB), Centre National de la Recherche Scientifique (CNRS)-Université de Franche-Comté (UFC), Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université de Bourgogne (UB), Max Planck Institute for Mathematics (MPIM), Max-Planck-Gesellschaft, ANR-10-LABX-0070,MILYON,Community of mathematics and fundamental computer science in Lyon(2010), and ANR-15-CE40-0012,GéoLie,Méthodes géométriques en théorie de Lie(2015)
Subjects: Polar representation, Symplectic variety, [ MATH.MATH-SG ] Mathematics [math]/Symplectic Geometry [math.SG], 01 natural sciences, Combinatorics, Mathematics - Algebraic Geometry, symbols.namesake, Morphism, 0103 physical sciences, FOS: Mathematics, 14L30, 53D20, 20G05, 20G20, 13A50, Representation Theory (math.RT), 0101 mathematics, MSC: 14L30, 53D20, 20G05, 20G20, 13A50, Mathematics::Representation Theory, Symplectic reduction, Algebraic Geometry (math.AG), Moment map, Mathematics, Weyl group, Algebra and Number Theory, Conjecture, [MATH.MATH-RT]Mathematics [math]/Representation Theory [math.RT], Reductive group, 010102 general mathematics, [MATH.MATH-SG]Mathematics [math]/Symplectic Geometry [math.SG], [ MATH.MATH-RT ] Mathematics [math]/Representation Theory [math.RT], [ MATH.MATH-AG ] Mathematics [math]/Algebraic Geometry [math.AG], Mathematics - Symplectic Geometry, symbols, Symplectic Geometry (math.SG), 010307 mathematical physics, Isomorphism, [MATH.MATH-AG]Mathematics [math]/Algebraic Geometry [math.AG], Mathematics - Representation Theory, Symplectic geometry
Abstract: If $(G,V)$ is a polar representation with Cartan subspace $\mathfrak c$ and Weyl group $W$, it is shown that there is a natural morphism of Poisson schemes $\mathfrak c \oplus {\mathfrak c}^*/W \to V\oplus V^*/\!\!/\!\!/ G$. This morphism is conjectured to be an isomorphism of the underlying reduced varieties if $(G,V)$ is visible. The conjecture is proved for visible stable locally free polar representations and certain further examples., Comment: 18 pages, final version
Published: 2017

12. Interactive Information Design

Author: Frédéric Koessler, Marie Laclau, Tristan Tomala, Paris School of Economics (PSE), École des Ponts ParisTech (ENPC)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Université Paris 1 Panthéon-Sorbonne (UP1)-Centre National de la Recherche Scientifique (CNRS)-École des hautes études en sciences sociales (EHESS)-Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE), Paris Jourdan Sciences Economiques (PJSE), Université Paris 1 Panthéon-Sorbonne (UP1)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-École des hautes études en sciences sociales (EHESS)-École des Ponts ParisTech (ENPC)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE), Groupement de Recherche et d'Etudes en Gestion (GREGHEC ), Ecole des Hautes Etudes Commerciales (HEC Paris)-Centre National de la Recherche Scientifique (CNRS), Ecole des Hautes Etudes Commerciales (HEC Paris), ANR-17-EURE-0001,PGSE,Ecole d'Economie de Paris(2017), Groupement de Recherche et d'Etudes en Gestion à HEC (GREGH), ANR-19-CE26-0010,StratCom,Diffusion de l'information en présence de rationalité limitée et de canaux de transmission complexes(2019), ANR-11-IDEX-0003,IPS,Idex Paris-Saclay(2011), ANR-11-LABX-0047,ECODEC,Réguler l'économie au service de la société(2011), ANR-15-CE38-0007,CIGNE,Communication et Information dans des Jeux dans des Réseaux(2015), Théorie économique, modélisation et applications (THEMA), Université de Cergy Pontoise (UCP), Université Paris-Seine-Université Paris-Seine-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS), HEC Research Paper Series, and Université Panthéon-Sorbonne (UP1)-École normale supérieure - Paris (ENS Paris)-Institut National de la Recherche Agronomique (INRA)-École des hautes études en sciences sociales (EHESS)-École des Ponts ParisTech (ENPC)-Centre National de la Recherche Scientifique (CNRS)
Subjects: TheoryofComputation_MISCELLANEOUS, Computer Science::Computer Science and Game Theory, Class (set theory), Computer science, General Mathematics, Bayesian persuasion, Management Science and Operations Research, Outcome (game theory), Subgame perfect equilibrium, Strategy, Information design, 0502 economics and business, Converse, statistical experiments, 050207 economics, 050205 econometrics, Mathematics, 05 social sciences, Normal-form game, Sharing rules, Pareto principle, TheoryofComputation_GENERAL, Statistical experiments, [SHS.ECO]Humanities and Social Sciences/Economics and Finance, Computer Science Applications, Splitting games, Bayes correlated equilibrium, JEL: C - Mathematical and Quantitative Methods/C.C7 - Game Theory and Bargaining Theory/C.C7.C72 - Noncooperative Games, [SHS.GESTION]Humanities and Social Sciences/Business administration, 050206 economic theory, JEL: D - Microeconomics/D.D8 - Information, Knowledge, and Uncertainty/D.D8.D82 - Asymmetric and Private Information • Mechanism Design, Mathematical economics
Abstract: We study the interaction between multiple information designers who try to influence the behavior of a set of agents. When the set of messages available to each designer is finite, such games always admit subgame perfect equilibria. When designers produce public information about independent pieces of information, every equilibrium of the direct game (in which the set of messages coincides with the set of states) is an equilibrium with larger (possibly infinite) message sets. The converse is true for a class of Markovian equilibria only. When designers produce information for their own corporation of agents, pure strategy equilibria exist and are characterized via an auxiliary normal form game. In an infinite-horizon multi-period extension of information design games, a feasible outcome which Pareto dominates a more informative equilibrium of the one-period game is supported by an equilibrium of the multi-period game.
Published: 2022

13. More efficient periodic traversal in anonymous undirected graphs

Author: Kunihiko Sadakane, Ioannis Lignos, Leszek Gsieniec, Ralf Klasing, Jesper Jansson, Stefan Dobrev, Russell Martin, David Ilcinkas, Wing-Kin Sung, Jurek Czyzowicz, Département d'Informatique et d'Ingénierie (DII), Université du Québec en Outaouais (UQO), Institute of Mathematics, Slovak Academy of Science [Bratislava] (SAS), Department of Computer Science [Liverpool], University of Liverpool, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Ochanomizu University, Department of Computer Science, Durham University, Principles of Informatics Research Division, National Institute of Informatics (NII), National University of Singapore (NUS), See paper for details, ANR-07-BLAN-0322,ALADDIN,Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks(2007), INRIA Futurs, See paper for details., ANR-05-MMSA-0006,ALPAGE,ALgorithmique des Plates-formes A Grande Echelle(2005), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), and Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest
Subjects: FOS: Computer and information sciences, General Computer Science, Discrete Mathematics (cs.DM), [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Comparability graph, Constant-memory agent, 0102 computer and information sciences, 02 engineering and technology, Strength of a graph, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Upper and lower bounds, law.invention, Theoretical Computer Science, Combinatorics, Graph exploration, law, Graph power, Line graph, Graph traversal, 0202 electrical engineering, electronic engineering, information engineering, Algorithms and data structures, Oblivious agent, Undirected graph, Mathematics, Discrete mathematics, Mobile entity, Voltage graph, Three-layer partition, Butterfly graph, Periodic graph traversal, Tree traversal, 010201 computation theory & mathematics, 020201 artificial intelligence & image processing, Periodic graph (geometry), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Null graph, Span tree, Period length, Computer Science - Discrete Mathematics, Computer Science(all)
Abstract: International audience; We consider the problem of periodic graph exploration in which a mobile entity with constant memory, an agent, has to visit all n nodes of an input simple, connected, undirected graph in a periodic manner. Graphs are assumed to be anonymous, that is, nodes are unlabeled. While visiting a node, the agent may distinguish between the edges incident to it; for each node v, the endpoints of the edges incident to v are uniquely identified by different integer labels called port numbers. We are interested in algorithms for assigning the port numbers together with traversal algorithms for agents using these port numbers to obtain short traversal periods. Periodic graph exploration is unsolvable if the port numbers are set arbitrarily; see Budach (1978) [1]. However, surprisingly small periods can be achieved by carefully assigning the port numbers. Dobrev et al. (2005) [4] described an algorithm for assigning port numbers and an oblivious agent (i.e., an agent with no memory) using it, such that the agent explores any graph with n nodes within the period 10n. When the agent has access to a constant number of memory bits, the optimal length of the period was proved in Gąsieniec et al. (2008) [7] to be no more than 3.75n−2 (using a different assignment of the port numbers and a different traversal algorithm). In this paper, we improve both these bounds. More precisely, we show how to achieve a period length of at most for oblivious agents and a period length of at most 3.5n−2 for agents with constant memory. To obtain our results, we introduce a new, fast graph decomposition technique called a three-layer partition that may also be useful for solving other graph problems in the future. Finally, we present the first non-trivial lower bound, 2.8n−2, on the period length for the oblivious case.
Published: 2012

14. Stability of optimal traffic plans in the irrigation problem

Author: Antoine Prouff, Antonio De Rosa, Andrea Marchese, Maria Colombo, Paul Pegon, Ecole Polytechnique Fédérale de Lausanne (EPFL), Courant Institute of Mathematical Sciences [New York] (CIMS), New York University [New York] (NYU), NYU System (NYU)-NYU System (NYU), Department of mathematics/Dipartimento di Matematica [Univ. Trento], Università degli Studi di Trento (UNITN), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), Méthodes numériques pour le problème de Monge-Kantorovich et Applications en sciences sociales (MOKAPLAN), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Ecole Normale Supérieure Paris-Saclay (ENS Paris Saclay), Maria Colombo was partially supported by the Swiss National Science Foundation grant 200021_182565. Antonio De Rosa has been supported by the NSF DMS Grant No. 1906451. Andrea Marchese acknowledges partial support from GNAMPA-INdAM., Department of Mathematics [College Park], University of Maryland [College Park], University of Maryland System-University of Maryland System, Bocconi Institute for Data Science and Analytics (BIDSA), Bocconi University [Milan, Italy], Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Inria de Paris, M. C. was partially supported by the Swiss National Science Foundation grant 200021_182565. A. D. R. has been supported by the NSF DMS Grant No. 1906451 and the NSF DMS Grant No. 2112311. A. M. acknowledges partial support from GNAMPA-INdAM. A.P. was supported by the Fondation Mathématiques Jacques Hadamard. P.P and A.P. both acknowledge EPFL for hosting them during the semester this paper was prepared., Inria de Paris, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CEntre de REcherches en MAthématiques de la DEcision (CEREMADE)
Subjects: BRANCHED TRANSPORT, Mathematical optimization, Irrigation, TRAFFIC PLANS, [MATH.MATH-CA]Mathematics [math]/Classical Analysis and ODEs [math.CA], 01 natural sciences, Stability (probability), symbols.namesake, Mathematics - Analysis of PDEs, Classical Analysis and ODEs (math.CA), FOS: Mathematics, Computer Science::Networking and Internet Architecture, [MATH.MATH-AP]Mathematics [math]/Analysis of PDEs [math.AP], Discrete Mathematics and Combinatorics, Limit (mathematics), 0101 mathematics, Mathematics - Optimization and Control, Mathematics, TRANSPORTATION NETWORK, BRANCHED TRANSPORT, IRRIGATION PROBLEM, TRAFFIC PLANS, STABILITY, STABILITY, IRRIGATION PROBLEM, Applied Mathematics, TRANSPORTATION NETWORK, 010102 general mathematics, Eulerian path, Flow network, 010101 applied mathematics, Optimization and Control (math.OC), Mathematics - Classical Analysis and ODEs, symbols, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Analysis, Lagrangian, Analysis of PDEs (math.AP)
Abstract: We prove the stability of optimal traffic plans in branched transport. In particular, we show that any limit of optimal traffic plans is optimal as well. This result goes beyond the Eulerian stability proved in [7], extending it to the Lagrangian framework.
Published: 2022

15. Modeling Interactions among Migration, Growth and Pressure in Tumor Dynamics

Author: Juan Campos, Juan José Soler, Juan Melchor, Beatriz Blanco, [Blanco, Beatriz] Univ Granada, Dept Struct Mech, Granada 18071, Spain, [Blanco, Beatriz] Ibs GRANADA, Inst Invest Biosanitaria, Granada 18012, Spain, [Melchor, Juan] Ibs GRANADA, Inst Invest Biosanitaria, Granada 18012, Spain, [Campos, Juan] Univ Granada, Fac Ciencias, Dept Matemat Aplicada, Granada 18071, Spain, [Soler, Juan] Univ Granada, Fac Ciencias, Dept Matemat Aplicada, Granada 18071, Spain, [Campos, Juan] Univ Granada, Res Unit Modelling Nat MNat, Granada 18071, Spain, [Melchor, Juan] Univ Granada, Res Unit Modelling Nat MNat, Granada 18071, Spain, [Soler, Juan] Univ Granada, Res Unit Modelling Nat MNat, Granada 18071, Spain, [Melchor, Juan] Univ Granada, Dept Stat & Operat Res, Granada 18071, Spain, MINECO-Feder (Spain), Junta de Andalucia (Spain), Instituto de Salud Carlos III, Ministry of Science, Innovation and Universities of Spain, Consejeria de Economia, Conocimiento, Empresas y Universidad, European Regional Development Fund (ERDF), [Blanco,B] Department of Structural Mechanics, University of Granada, Granada, Spain. [Blanco,B, Melchor,J] Instituto de Investigación Biosanitaria, ibs.GRANADA, Granada, Spain. [Campos,J, Soler,J] Departamento de Matemática Aplicada, Facultad de Ciencias, Universidad de Granada, Granada, Spain. [Campos,J, Melchor,J, Soler,J] Research Unit 'Modelling Nature' (MNat), Universidad de Granada, Granada, Spain., and This paper has been partially supported by the MINECO-Feder (Spain) research grant num bers RTI2018-098850-B-I00 (J.C., J.S.) & EQC2018-004508-P (B.B., J.M.), the Junta de Andalucía (Spain) Projects PY18-RT-2422 (J.C., J.S.), A-FQM-311-UGR18 (J.C., J.S.) & IE2017-5537 (B.B., J.M.), and by the Instituto de Salud Carlos III, project number DTS17/00087 (J.M., J.S.). This study was also funded by Ministry of Science, Innovation and Universities of Spain, project numbers DPI2017-85359-R (B.B., J.M.) & PID2019-106947RA-C22 (B.B., J.M.) and by Consejería de Economía, Conocimiento, Empresas y Universidad and European Regional Development Fund (ERDF), ref. SOMM17/6109/UGR (J.C., J.M., J.S.). Lastly, B.B. research was granted by Ministry of Science, Innovation and Universities of Spain, FPU2017/01415.
Subjects: Computer science, 01 natural sciences, Forces, Phenomena and Processes::Cell Physiological Phenomena::Cell Physiological Processes::Cell Movement [Medical Subject Headings], Diffusion, porous media, Qualitative behavior, Computer Science (miscellaneous), Numerical simulations, Homeostasis, Statistical physics, Diffusion (business), Solid tumor, Analytical, Diagnostic and Therapeutic Techniques and Equipment::Investigative Techniques::Epidemiologic Methods::Data Collection::Vital Statistics::Mortality::Cause of Death [Medical Subject Headings], Cancer, 0303 health sciences, Partial differential equation, Mathematical modelling, Dynamics (mechanics), Traveling-waves, mathematical modeling, tumor dynamics, Phenomena and Processes::Chemical Phenomena::Biochemical Phenomena::Biochemical Processes::Signal Transduction [Medical Subject Headings], Diseases::Neoplasms [Medical Subject Headings], flux-saturated, Modelos teóricos, General Mathematics, Phenomena and Processes::Physical Phenomena::Mechanical Phenomena::Porosity [Medical Subject Headings], Context (language use), Information Science::Information Science::Communication::Cybernetics::Feedback [Medical Subject Headings], cell motility, Stress, Mechanics, 03 medical and health sciences, QA1-939, Hele-Shaw model, Movimiento celular, Phenomena and Processes::Physical Phenomena::Mechanical Phenomena::Elasticity [Medical Subject Headings], 0101 mathematics, Engineering (miscellaneous), 030304 developmental biology, Computer simulation, 010102 general mathematics, Porous-media equations, Mass, numerical simulation, Floculadores, Phenomena and Processes::Cell Physiological Phenomena::Cell Physiological Processes::Cell Transdifferentiation::Epithelial-Mesenchymal Transition [Medical Subject Headings], mechanical feedback, Phenomena and Processes::Physiological Phenomena::Physiological Processes::Homeostasis [Medical Subject Headings], Mathematics
Abstract: What are the biomechanical implications in the dynamics and evolution of a growing solid tumor? Although the analysis of some of the biochemical aspects related to the signaling pathways involved in the spread of tumors has advanced notably in recent times, their feedback with the mechanical aspects is a crucial challenge for a global understanding of the problem. The aim of this paper is to try to illustrate the role and the interaction between some evolutionary processes (growth, pressure, homeostasis, elasticity, or dispersion by flux-saturated and porous media) that lead to collective cell dynamics and defines a propagation front that is in agreement with the experimental data. The treatment of these topics is approached mainly from the point of view of the modeling and the numerical approach of the resulting system of partial differential equations, which can be placed in the context of the Hele-Shaw-type models. This study proves that local growth terms related to homeostatic pressure give rise to retrograde diffusion phenomena, which compete against migration through flux-saturated dispersion terms., MINECO-Feder (Spain) research grant numbers RTI2018-098850-B-I00 (J.C., J.S.) & EQC2018-004508-P (B.B., J.M.), Junta de Andalucía (Spain) Projects PY18-RT-2422 (J.C., J.S.), A-FQM-311-UGR18 (J.C., J.S.) & IE2017-5537 (B.B., J.M.), Instituto de Salud Carlos III, project number DTS17/00087 (J.M., J.S.), Ministry of Science, Innovation and Universities of Spain, project numbers DPI2017-85359-R (B.B., J.M.) & PID2019-106947RA-C22 (B.B., J.M.), Consejería de Economía, Conocimiento, Empresas y Universidad and European Regional Development Fund (ERDF), ref. SOMM17/6109/UGR (J.C., J.M., J.S.), Ministry of Science, Innovation and Universities of Spain, FPU2017/01415
Published: 2021

16. Some analytical solutions for validation of free surface flow computational codes

Author: Bernard Di Martino, Fabien Souillé, Jacques Sainte-Marie, Marie-Odile Bristeau, Anne Mangeney, Numerical Analysis, Geophysics and Ecology (ANGE), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Jacques-Louis Lions (LJLL (UMR_7598)), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), Institut de Physique du Globe de Paris (IPGP (UMR_7154)), Institut national des sciences de l'Univers (INSU - CNRS)-Université de La Réunion (UR)-Institut de Physique du Globe de Paris (IPG Paris)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), The work presented in this paper was supported in part by the ANR Mimosa (ANR-14-CE01-0012) and ERC contract ERC-CG-2013-PE10-617472 SLIDEQUAKES. The authors also acknowledge the Inria Project Lab 'Algae in Silico' for its financial support., ANR-14-CE01-0012,MIMOSA,Analyse, modélisation et utilisation du bruit sismique large bande: des microséismes aux oscillations libres de la terre(2014), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP), Institut de Physique du Globe de Paris (IPGP), Institut national des sciences de l'Univers (INSU - CNRS)-IPG PARIS-Université de La Réunion (UR)-Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP), Université Paris Diderot - Paris 7 (UPD7)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), and Centre National de la Recherche Scientifique (CNRS)-Université de La Réunion (UR)-Université Paris Diderot - Paris 7 (UPD7)-IPG PARIS-Institut national des sciences de l'Univers (INSU - CNRS)
Subjects: 010103 numerical & computational mathematics, Analytical solutions, 01 natural sciences, law.invention, Physics::Fluid Dynamics, Free surface Euler equations, symbols.namesake, law, [MATH.MATH-AP]Mathematics [math]/Analysis of PDEs [math.AP], Boundary value problem, [PHYS.MECA.MEFL]Physics [physics]/Mechanics [physics]/Fluid mechanics [physics.class-ph], 0101 mathematics, [MATH]Mathematics [math], Mathematics, Computer simulation, [PHYS.MECA.MEFL]Physics [physics]/Mechanics [physics]/Mechanics of the fluids [physics.class-ph], Mechanical Engineering, Mechanics, Euler system, Condensed Matter Physics, River dynamics, Euler equations, 010101 applied mathematics, Flow (mathematics), Mechanics of Materials, Free surface, symbols, Compressibility, Hydrostatic equilibrium
Abstract: We present several time dependent analytical solutions for the incompressible Euler system with free surface. These analytical solutions give quantitative descriptions of some physical phenomena and can be used as reference solutions when validating numerical simulation codes. They concern fluid flows governed by Euler equations with or withouthydrostatic hypothesis including wet/dry interface, variable density, wide variety of boundary conditions and possibly non-uniform bottom topographies. Some of these analytical solutions concern shallow water type models or free surface Navier-Stokes model i.e. with a viscous fluid.
Published: 2021

17. Accounting for competition in multi-environment tree genetic evaluations: a case study with hybrid pines

Author: Nuno Borralho, Eduardo P. Cappa, Ector Belaber, Maria Elena Gauchat, Cristian Damián Schoffen, Facundo Muñoz, Leopoldo Sanchez, Instituto Nacional de Tecnología Agropecuaria (INTA), Consejo Nacional de Investigaciones Científicas y Técnicas [Buenos Aires] (CONICET), Animal, Santé, Territoires, Risques et Ecosystèmes (UMR ASTRE), Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad)-Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE), Département Systèmes Biologiques (Cirad-BIOS), Centre de Coopération Internationale en Recherche Agronomique pour le Développement (Cirad), RAIZ – Forestry & Paper Research Institut, Instituto Superior Técnico, Universidade Técnica de Lisboa, Biologie intégrée pour la valorisation de la diversité des Arbres et de la Forêt (BioForA), Office National des Forêts (ONF)-Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE), and This study was funded by the National Institute of Agricultural Technology (INTA) (grant numbers PNFOR-01104062, MSNES-1242204/5). E.P.C.’s research was partially supported by the National Agency for the Promotion of Science and Technology of Argentina (ANPCYT, PICT-2016 1048). F.M.’s research is partially supported by research grant MTM2016-77501-P from the State Research Agency of the Spanish Ministry of Science, Innovation and Universities jointly with the European Regional Development Fund, FEDER.
Subjects: Additive and competition genotype–environment interaction, 0106 biological sciences, Mixed model, [SDV]Life Sciences [q-bio], media_common.quotation_subject, Accounting, Tree breeding, 010603 evolutionary biology, 01 natural sciences, Genetic correlation, Competition (biology), Competition model, Genetic variation, Gene–environment interaction, media_common, Mathematics, [SDV.EE]Life Sciences [q-bio]/Ecology, environment, Ecology, business.industry, Diameter at breast height, Forestry, 15. Life on land, Total heritable variance, [SDE.BE]Environmental Sciences/Biodiversity and Ecology, business, 010606 plant biology & botany
Abstract: International audience; Key message: A novel multi-environment competition individual-tree mixed model resulted in better fit, and greater individual narrow- and broad-sense heritabilities than the model without competition, notably for traits showing competition. In multi-environment tests, the proposed model would allow tree breeders to select genotypes with the best performance in both additive direct and competition breeding values, increasing forest productivity. Context: Genetic merit of trees is known to be affected and interact with local competition effects as well as changes across environmental conditions. Recent studies showed that competition genetic effects can affect the genetic variance and bias the tree breeding values, and its covariance with direct breeding values has been variable across traits. Aims: The present paper extends a mixed-model methodology to the problem of accounting for competition in a multi-environment set of forest genetic trials and exploring its impact on genetic variances as well as the multi-environment genetic correlation. Methods: The proposed model is illustrated using data from two full-sib trials of Pinus elliottii var. elliottii × Pinus caribaea var. hondurensis F1. Dispersion parameters and (co)variance of total breeding values were estimated for diameter at breast height, total tree height, and stem straightness at age 10. Results: For traits showing competition effects (diameter at breast height and total tree height), the proposed multi-environment competition model gave better fit than the simpler model. Accounting for competition increased the direct additive variance, reduced the residual variances, and did not change significantly the across-site additive genetic correlation. However, for diameter at breast height, top 5% best genetic rankings showed differences. Conclusion: When traits are strongly affected by inter-tree competition, the use of the proposed model in multi-environment analyses can efficiently identify the phenomenon with general benefits in the fitting of genetic components and open the door to select on the basis of competitiveness.
Published: 2021

18. The DGDD Method for Reduced-Order Modeling of Conservation Laws

Author: Angelo Iollo, Charbel Farhat, Sebastian Grimberg, Michel Bergmann, Sébastien Riffaud, Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS), Modeling Enablers for Multi-PHysics and InteractionS (MEMPHIS), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Department of Aeronautics and Astronautics [Stanford] (AA Stanford), Stanford University, Department of Mechanical Engineering [Stanford], Institute for Computational and Mathematical Engineering [Stanford] (ICME), This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement N° 872442. Experiments presented in this paper were carried out using the PlaFRIM experimental testbed, supported by Inria, CNRS (LABRI and IMB), Université de Bordeaux, Bordeaux INP and Conseil Régional d’Aquitaine (see https://www.plafrim.fr/)., Plafrim, MEMPHIS, European Project: 872442,ARIA, European Project: 872442,ARIA(2019), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS), and Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest
Subjects: ECSW method, Polynomial, Physics and Astronomy (miscellaneous), Proper Orthogonal Decomposition, 010103 numerical & computational mathematics, 01 natural sciences, symbols.namesake, Discontinuous Galerkin method, Applied mathematics, Domain decomposition, 0101 mathematics, Representation (mathematics), Parametric statistics, Mathematics, Numerical Analysis, Conservation law, Applied Mathematics, Domain decomposition methods, [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation, Computer Science Applications, Euler equations, 010101 applied mathematics, Reduced-order model, Computational Mathematics, Modeling and Simulation, symbols, Reduction (mathematics), [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA]
Abstract: International audience; The discontinuous Galerkin domain decomposition (DGDD) method couples subdomains of high-fidelity polynomial approximation to regions of low-dimensional resolution for the numerical solution of systems of conservation laws. In the low-fidelity regions, the solution is approximated by empirical modes constructed by Proper Orthogonal Decomposition and a reduced-order model is used to predict the solution. The high-dimensional model instead solves the system of conservation laws only in regions where the solution is not amenable to a low-dimensional representation. The coupling between the high-dimensional and the reduced-order models is then performed in a straightforward manner through numerical fluxes at discrete cell boundaries. We show results from application of the proposed method to parametric problems governed by the quasi-1D and 2D compressible Euler equations. In particular, we investigate the prediction of unsteady flows in a converging-diverging nozzle and over a NACA0012 airfoil in presence of shocks. The results demonstrate the stability and the accuracy of the proposed method and the significant reduction of the computational cost with respect to the high-dimensional model.
Published: 2021

19. Multidimensional inequality and inframodular order

Author: Alain Chateauneuf, Zaier Aouani, Department of economics, University of Kansas, University of Kansas [Lawrence] (KU), IPAG Business School, Centre d'économie de la Sorbonne (CES), Université Paris 1 Panthéon-Sorbonne (UP1)-Centre National de la Recherche Scientifique (CNRS), Paris School of Economics (PSE), École des Ponts ParisTech (ENPC)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Université Paris 1 Panthéon-Sorbonne (UP1)-Centre National de la Recherche Scientifique (CNRS)-École des hautes études en sciences sociales (EHESS)-Institut National de Recherche pour l’Agriculture, l’Alimentation et l’Environnement (INRAE), This paper is part of the research project ANR ‘‘Mesure des inégalités ordinales et multidimensionnelles’’ (ORDINEQ) of the French National Research Agency (Agence Nationale de la Recherche), whose financial support is gratefully acknowledged., and ANR-16-CE41-0005,ORDINEQ,La Mesure des Inégalités Ordinales et Multidimensionnelles(2016)
Subjects: Economics and Econometrics, education.field_of_study, Multi-attribute inequality, Inequality, Applied Mathematics, media_common.quotation_subject, 05 social sciences, Population, [SHS.ECO]Humanities and Social Sciences/Economics and Finance, Inframodular functions, Multidimensional Pigou–Dalton transfers, Order (business), 0502 economics and business, Econometrics, Inframodular order, 050207 economics, education, 050205 econometrics, media_common, Mathematics
Abstract: International audience; Motivated by the pertinence of Pigou–Dalton (PD) transfers for inequality measurement when only one attribute is involved, we show that inframodular functions are consistent with multidimensional PD transfers and that weakly inframodular functions fit more accurately with the traditional notion of PD transfers. We emphasize, for inequality rankings of allocations of multiple attributes in a population, the similarities of the inframodular order, defined using inframodular functions, with the concave order in the unidimensional framework.
Published: 2020

20. On the complexity of computing integral bases of function fields

Author: Simon Abelard, Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), David R. Cheriton School of Computer Science, University of Waterloo [Waterloo], This paper is a part of a project that has received funding by the French Agence de l'Innovation de Défense (DGA)., Boulier F., England M., Sadykov T.M., and Vorozhtsov E.V.
Subjects: Algebraic function field, Computer Science - Symbolic Computation, FOS: Computer and information sciences, [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], 050101 languages & linguistics, Plane curve, [MATH.MATH-AC]Mathematics [math]/Commutative Algebra [math.AC], 02 engineering and technology, Symbolic Computation (cs.SC), Commutative Algebra (math.AC), Puiseux series, Mathematics - Algebraic Geometry, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, Polynomial matrices, 0202 electrical engineering, electronic engineering, information engineering, FOS: Mathematics, 0501 psychology and cognitive sciences, Linear algebra, Algebraic Geometry (math.AG), Mathematics, Discrete mathematics, [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], Irreducible polynomial, 05 social sciences, Basis (universal algebra), Function (mathematics), Mathematics - Commutative Algebra, 020201 artificial intelligence & image processing, [MATH.MATH-AG]Mathematics [math]/Algebraic Geometry [math.AG], Monic polynomial
Abstract: Let $\mathcal{C}$ be a plane curve given by an equation $f(x,y)=0$ with $f\in K[x][y]$ a monic squarefree polynomial. We study the problem of computing an integral basis of the algebraic function field $K(\mathcal{C})$ and give new complexity bounds for three known algorithms dealing with this problem. For each algorithm, we study its subroutines and, when it is possible, we modify or replace them so as to take advantage of faster primitives. Then, we combine complexity results to derive an overall complexity estimate for each algorithm. In particular, we modify an algorithm due to B\"ohm et al. and achieve a quasi-optimal runtime., Comment: Preliminary version
Published: 2020

21. Sub-quadratic time for Riemann-Roch spaces. The case of smooth divisors over nodal plane projective curves

Author: Alain Couvreur, Grégoire Lecerf, Simon Abelard, Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), Geometry, arithmetic, algorithms, codes and encryption (GRACE), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), This paper is a part of a project that has received funding by the French Agence de l'Innovation de Défense (DGA)., Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Inria Saclay - Ile de France, Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), and Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)
Subjects: Projective curve, [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC], [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Pure mathematics, Basis (linear algebra), Plane (geometry), 010102 general mathematics, MathematicsofComputing_NUMERICALANALYSIS, 010103 numerical & computational mathematics, Space (mathematics), 01 natural sciences, Riemann hypothesis, symbols.namesake, Mathematics::Algebraic Geometry, TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY, ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION, symbols, Algebraic curve, [MATH.MATH-AG]Mathematics [math]/Algebraic Geometry [math.AG], 0101 mathematics, Projective test, Time complexity, Mathematics
Abstract: International audience; We revisit the seminal Brill-Noether algorithm in the rather generic situation of smooth divisors over a nodal plane projective curve. Our approach takes advantage of fast algorithms for polynomials and structured matrices. We reach sub-quadratic time for computing a basis of a Riemann-Roch space. This improves upon previously known complexity bounds.
Published: 2020

22. Online estimation of integrated squared density derivatives

Author: Abdelkader Mokkadem, Mariane Pelletier, Laboratoire de Mathématiques de Versailles (LMV), Université de Versailles Saint-Quentin-en-Yvelines (UVSQ)-Université Paris-Saclay-Centre National de la Recherche Scientifique (CNRS), and We deeply thank the Referees for their thoughtful remarks, which led to a substantially improved version of our paper.
Subjects: Statistics and Probability, Recursive estimation, Mean squared error, 010102 general mathematics, Bandwidth (signal processing), Estimator, Probability density function, Density estimation, Online estimation, Rate of convergence, Stochastic algorithm, 01 natural sciences, 010104 statistics & probability, Kernel estimators of integrals, [MATH.MATH-ST]Mathematics [math]/Statistics [math.ST], Applied mathematics, 0101 mathematics, Statistics, Probability and Uncertainty, Mathematics, Parametric statistics
Abstract: Hall and Marron (1987) introduced kernel estimators of integrals of the squared m -order derivatives of a probability density. Mokkadem and Pelletier (2020) gave recursive versions of their estimators, but the main drawback of these estimators is that their update requires the use of all past data. The aim of this paper is the study of online versions of the estimators introduced by Hall and Marron (1987), that is of estimators which are not only recursive, but which also have the property that their update uses only the last available data. Rates of convergence in mean squared error (MSE) are calculated. Similarly to the estimators of Hall and Marron (1987) and of Mokkadem and Pelletier (2020), our online estimators achieve the parametric rate n − 1 when m = 0 or when higher order kernels are used. For the case when the parametric rate is not obtained, we also study an online version of the estimator proposed by Jones and Sheather (1991). Finally, we provide recursive estimators of the optimal bandwidth in the framework of density estimation.
Published: 2020

23. Geometry description and mesh construction from medical imaging

Author: Silvia Bertoluzza, Minh Phan, Michela Spagnuolo, Philippe Ricka, Micol Pennacchio, Giuseppe Patanè, Michele Giuliano Carlino, Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS), Modeling Enablers for Multi-PHysics and InteractionS (MEMPHIS), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Institut de Recherche Mathématique Avancée (IRMA), Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA), Institut de Mathématiques de Toulon - EA 2134 (IMATH), Université de Toulon (UTLN), Istituto di Matematica Applicata e Tecnologie Informatiche (IMATI), Consiglio Nazionale delle Ricerche (CNR), Istituto di Matematica Applicata e Tecnologie Informatiche (IMATI-CNR), Consiglio Nazionale delle Ricerche [Roma] (CNR), his paper has been realized in the framework of ERC Project CHANGE, which has received funding from the EuropeanResearch Council (ERC) under the European Unions Horizon 2020 research and innovation programme (grant agreement No694515., European Project: 8509436(1986), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, Université de Strasbourg (UNISTRA)-Centre National de la Recherche Scientifique (CNRS), and National Research Council of Italy | Consiglio Nazionale delle Ricerche (CNR)
Subjects: T57-57.97, Applied mathematics. Quantitative methods, Computer simulation, Computer science, business.industry, Atlas (topology), ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION, Image segmentation, Modular design, Reference image, N/A, QA1-939, Medical imaging, [INFO.INFO-IM]Computer Science [cs]/Medical Imaging, A priori and a posteriori, Computer vision, [INFO]Computer Science [cs], Artificial intelligence, business, Mathematics, ComputingMethodologies_COMPUTERGRAPHICS
Abstract: International audience; We present a new method for defining and meshing patient-specific domains from medical images. Our approach is based on an atlas image segmentation technique, and relies on the modular registration algorithm of S. Bertoluzza et al. [25]. The mesh of the patient-specific domain is generated by deforming the corresponding mesh on an a priori segmented and meshed reference image (the atlas). Our method aims at automating the process at the interface of medical imaging and numerical simulation, thus reducing the computational cost in those situations where simulations have to be managed on numerous medical images of similar patients.; Nous présentons une nouvelle méthode de reconnaissance et de maillage d’un domaine d’intérêt d’une image médicale. Notre approche se base sur une méthode de segmentation à partir d’un atlas, et dépend de la boîte à outils modulaire pour la co-registration d’images développée par S. Bertoluzza et al. [25]. Le maillage du domaine spécifique au patient est généré par déformation du maillage correspondant sur une image de référence segmentée a priori (l’atlas). Notre méthode vise à automatiser le processus à l’interface entre l’imagerie médicale et la simulation numérique, avec pour but de réduire le coût de calcul dans les situations dans lesquelles des simulations doivent être faites sur de nombreuses images similaires.
Published: 2020

24. About strong string stability of a vehicle chain with time-headway control

Author: Alain Sarlette, Arash Farnam, Universiteit Gent = Ghent University [Belgium] (UGENT), QUANTum Information Circuits (QUANTIC), MINES ParisTech - École nationale supérieure des mines de Paris, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Sorbonne Université (SU)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), This paper presents research results of the Belgian Network DYSCO (Dynamical Systems, Control, and Optimization), funded by the Interuniversity Attraction Poles Programme, initiated by the Belgian State, Science Policy Office., École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-MINES ParisTech - École nationale supérieure des mines de Paris, Universiteit Gent = Ghent University (UGENT), Mines Paris - PSL (École nationale supérieure des mines de Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Sorbonne Université (SU)-Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire de physique de l'ENS - ENS Paris (LPENS), Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)-Département de Physique de l'ENS-PSL, École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité)-Département de Physique de l'ENS-PSL, Université Paris sciences et lettres (PSL), and Sarlette, Alain
Subjects: Time headway, 050210 logistics & transportation, 0209 industrial biotechnology, String length, Technology and Engineering, Proportional derivative, SUBJECT, PLATOONS, 05 social sciences, [MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC], 02 engineering and technology, Chain length, 020901 industrial engineering & automation, Control theory, Optimization and Control (math.OC), Norm (mathematics), Bounded function, [INFO.INFO-AU]Computer Science [cs]/Automatic Control Engineering, 0502 economics and business, FOS: Mathematics, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Absolute velocity, Mathematics - Optimization and Control, [INFO.INFO-AU] Computer Science [cs]/Automatic Control Engineering, Mathematics
Abstract: This paper deals with the problem of string stability in a chain of acceleration-controlled vehicles, i.e. how input disturbances affect the distributed system for very long chains. There exist variants of string stability, like avoiding that a local disturbance gets amplified along the chain, or more strongly ensuring that the output vector's p-norm remains bounded for any bounded vector of input disturbances independently of the string length. They are all impossible to achieve with any linear controller if the vehicles only use relative information of few vehicles in front. Previous work has shown that adding absolute velocity into the controller, allows to at least avoid amplification of a local disturbance. In this paper, we consider the stronger definitions of string stability, under this same relaxation of using absolute velocity in the controller. We prove that the influence from input vector to output vector cannot be bounded independently of chain length in the most popular 2-norm sense, with any bounded stabilizing linear controller; while a proportional derivative (PD) controller can guarantee it in the practically relevant infinity-norm sense. Moreover, we identify the disturbance acting on the leader as the main issue for string stability., Comment: presented at IEEE-CDC 2018, Miami; more complete version and correcting a few typos
Published: 2019

25. Algebraic and topological structures on rational tangles

Author: Seyed M.H. Mansourbeigi, Vida Milani, Hossein Finizadeh, and Poli Paper
Subjects: tangle convergent, Coalgebra, Structure (category theory), Bi-pseudo-module, 010103 numerical & computational mathematics, Interval (mathematics), lcsh:Analysis, Group Hopf algebra, Continued fraction, Topology, 01 natural sciences, Tangle, Interval coalgebra, Incidence algebra, Mathematics::Quantum Algebra, Physical Sciences and Mathematics, Order (group theory), 0101 mathematics, Algebraic number, Mathematics, group Hopf algebra, Computer Sciences, lcsh:Mathematics, lcsh:QA299.6-433, Tangle convergen, bi-pseudo-module, lcsh:QA1-939, Mathematics::Geometric Topology, continued fraction, 010101 applied mathematics, Algebra, incidence algebra, pseudo-tensor product, Pseudo-tensor product, Pseudo-module, pseudo-module, Geometry and Topology, tangle, Locally finite partial order, locally finite partial order, interval coalgebra
Abstract: In this paper we present the construction of a group Hopf algebra on the class of rational tangles. A locally finite partial order on this class is introduced and a topology is generated. An interval coalgebra structure associated with the locally finite partial order is specified. Irrational and real tangles are introduced and their relation with rational tangles are studied. The existence of the maximal real tangle is described in detail.
Published: 2017

26. Minimal NMR distance information for rigidity of protein graphs

Author: Leo Liberti, Benjamin Bardiaux, Michael Nilges, Thérèse E. Malliavin, Bradley Worley, Bruce R. Donald, Carlile Lavor, Instituto de Matemática, Estatística e Computação Científica [Brésil] (IMECC), Universidade Estadual de Campinas (UNICAMP), Laboratoire d'informatique de l'École polytechnique [Palaiseau] (LIX), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), Duke University [Durham], Bioinformatique structurale, Institut Pasteur [Paris]-Centre National de la Recherche Scientifique (CNRS), C.L. would like to thank the Brazilian research agencies CNPq, FAPESP and B.D. would like to thank the NIH grants R01 GM-118543 and R01 GM-078031 for their financial support., We are also thankful to Angela Gronenborn and Michael Souza, for discussions that clarify some ideas in the paper, and to anonymous referees that made very important comments to this work., Bioinformatique structurale - Structural Bioinformatics, Universidade Estadual de Campinas = University of Campinas (UNICAMP), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), and Institut Pasteur [Paris] (IP)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Computational complexity theory, Nuclear Magnetic Resonance, 0211 other engineering and technologies, Structure (category theory), Rigidity (psychology), 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Topology, 01 natural sciences, Article, Cardinality, Protein structure, Distance Geometry, Discrete Mathematics and Combinatorics, Molecule, Combinatorial search, Mathematics, Quantitative Biology::Biomolecules, [SDV.BBM.BS]Life Sciences [q-bio]/Biochemistry, Molecular Biology/Structural Biology [q-bio.BM], Applied Mathematics, Solution set, 021107 urban & regional planning, [SDV.BBM.BP]Life Sciences [q-bio]/Biochemistry, Molecular Biology/Biophysics, [SDV.BBM.BS]Life Sciences [q-bio]/Biochemistry, Molecular Biology/Biomolecules [q-bio.BM], Vertex orders, 010201 computation theory & mathematics, [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], Molecular structure
Abstract: International audience; Nuclear Magnetic Resonance (NMR) experiments provide distances between nearby atoms of a protein molecule. The corresponding structure determination problem is to determine the 3D protein structure by exploiting such distances. We present a new order on the atoms of the protein, based on information from the chemistry of proteins and NMR experiments, which allows us to formulate the problem as a combinatorial search. Additionally, this order tells us what kind of NMR distance information is crucial to understand the cardinality of the solution set of the problem and its computational complexity.
Published: 2019

27. Multidimensional stability of V-shaped traveling fronts in time periodic bistable reaction–diffusion equations

Author: Wei-Jie Sheng, Department of Mathematics (HIT Harbin Institute of Technology), Harbin Institute of Technology (HIT), Institut de Mathématiques de Marseille (I2M), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), and This paper was supported by NSF of China (11401134) and by China Scholarship Council for a one year visit of Aix Marseille Université.
Subjects: Current (mathematics), Bistability, 010102 general mathematics, Mathematical analysis, Time periodic V-shaped traveling fronts, 01 natural sciences, Stability (probability), 010101 applied mathematics, Bistable, Computational Mathematics, Computational Theory and Mathematics, Two-dimensional space, Reaction diffusion equations, Modeling and Simulation, Stability theory, Bounded function, Reaction–diffusion system, [MATH.MATH-AP]Mathematics [math]/Analysis of PDEs [math.AP], Initial value problem, 0101 mathematics, Nonlinear Sciences::Pattern Formation and Solitons, Multidimensional stability, Mathematics
Abstract: International audience; This paper deals with the multidimensional stability of time periodic V-shaped traveling fronts in bistable reaction–diffusion equations. It is well known that time periodic V-shaped traveling fronts are asymptotically stable in two dimensional space. In the current study, we further show that such fronts are asymptotically stable under spatially decaying initial perturbations in Rn with n≥3. In particular, we show that the fronts are algebraically stable if the initial perturbations belong to L1 in a certain sense. Furthermore, we prove that there exists a solution oscillating permanently between two time periodic V-shaped traveling fronts, which implies that time periodic V-shaped traveling fronts are not always asymptotically stable under general bounded perturbations. Finally we show that time periodic V-shaped traveling fronts are only time global solutions of the Cauchy problem if the initial perturbations lie between two time periodic V-shaped traveling fronts.
Published: 2016

28. Psychophysical Foundations of the Cobb-Douglas Utility Function

Author: Rossella Argenziano, Itzhak Gilboa, Department of Economics, University of Essex, Groupement de Recherche et d'Etudes en Gestion à HEC (GREGH), Ecole des Hautes Etudes Commerciales (HEC Paris)-Centre National de la Recherche Scientifique (CNRS), and HEC Research Paper Series
Subjects: Simple (abstract algebra), Psychophysics, Literal interpretation, Independence (mathematical logic), Cobb-Douglas, [SHS.GESTION]Humanities and Social Sciences/Business administration, Function (mathematics), Semi-Order, CobB, Mathematical economics, JEL: D - Microeconomics/D.D1 - Household Behavior and Family Economics/D.D1.D11 - Consumer Economics: Theory, Mathematics, Weber's Law
Abstract: Relying on a literal interpretation of Weber's law in psychophysics, we show that a simple condition of independence across good categories implies the Cobb-Douglas preferences.
Published: 2018

29. A test for gene-environment interaction in the presence of measurement error in the environmental variable

Author: Hugues Aschard, Donna Spiegelman, Molin Wang, Vincent Laville, Pete Kraft, Centre de Bioinformatique, Biostatistique et Biologie Intégrative (C3BI), Institut Pasteur [Paris]-Centre National de la Recherche Scientifique (CNRS), Harvard T.H. Chan School of Public Health, The authors thank the reviewers for their helpful comments that have improved the paper. This research is supported by grant R01CA050597 from the National Cancer Institute (NCI) and R21HG007687 from the National Human Genome Research Institute (NHGRI). The authors have no conflict of interest to declare., and Institut Pasteur [Paris] (IP)-Centre National de la Recherche Scientifique (CNRS)
Subjects: 0301 basic medicine, Epidemiology, Genome-wide association study, Breast Neoplasms, MESH: Logistic Models, Interaction, Logistic regression, 01 natural sciences, Article, Correlation, 010104 statistics & probability, 03 medical and health sciences, Bias, Statistics, Linear regression, MESH: Bias, Humans, normal discriminant analysis, MESH: Genetic Variation, MESH: Models, Genetic, 0101 mathematics, Gene–environment interaction, gene-environment interaction test, Genetics (clinical), Mathematics, [STAT.AP]Statistics [stat]/Applications [stat.AP], Observational error, MESH: Humans, Models, Genetic, Genetic Variation, Reproducibility of Results, MESH: Gene-Environment Interaction, Linear discriminant analysis, 3. Good health, MESH: Reproducibility of Results, 030104 developmental biology, Logistic Models, [SDV.GEN.GH]Life Sciences [q-bio]/Genetics/Human genetics, genome-wide association studies, MESH: Genome-Wide Association Study, Gene-Environment Interaction, [SDV.SPEE]Life Sciences [q-bio]/Santé publique et épidémiologie, [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM], [STAT.ME]Statistics [stat]/Methodology [stat.ME], measurement error, MESH: Breast Neoplasms, Genome-Wide Association Study
Abstract: International audience; The identification of gene-environment interactions in relation to risk of human diseases has been challenging. One difficulty has been that measurement error in the exposure can lead to massive reductions in the power of the test, as well as in bias toward the null in the interaction effect estimates. Leveraging previous work on linear discriminant analysis, we develop a new test of interaction between genetic variants and a continuous exposure that mitigates these detrimental impacts of exposure measurement error in ExG testing by reversing the role of exposure and the diseases status in the fitted model, thus transforming the analysis to standard linear regression. Through simulation studies, we show that the proposed approach is valid in the presence of classical exposure measurement error as well as when there is correlation between the exposure and the genetic variant. Simulations also demonstrated that the reverse test has greater power compared to logistic regression. Finally, we confirmed that our approach eliminates bias from exposure measurement error in estimation. Computing times are reduced by as much as fivefold in this new approach. For illustrative purposes, we applied the new approach to an ExGWAS study of interactions with alcohol and body mass index among 1,145 cases with invasive breast cancer and 1,142 controls from the Cancer Genetic Markers of Susceptibility study.
Published: 2018

30. Convergence regions for the Chebyshev–Halley family

Author: B. Campos, Jordi Canela, P. Vindel, and The authors would like to thank the anonymous referees for their suggestions and comments, which improved this paper. The first and third authors were supported by the Spanish project MTM2014-52016-C02-2-P, the Generalitat Valenciana Project PROMETEO/2016/089 and UJI project P1.1B20115-16. The second author was supported by RedIUM and MINECO (Spain) through the research network MTM2014-55580-REDT and by the mathematics institute IMAC (Castellon, Spain).
Subjects: roots, Numerical Analysis, Pure mathematics, Chebyshev–Halley family, Iterative method, polynomials, Applied Mathematics, Chebyshev systems, 010102 general mathematics, 010103 numerical & computational mathematics, dynamics, Parameter space, Fixed point, 01 natural sciences, Attraction, Chebyshev filter, Critical point (mathematics), Combinatorics, Quadratic equation, Modeling and Simulation, Polinomis, 0101 mathematics, Sistemes de Chebyshev, Mathematics
Abstract: In this paper we study the dynamical behavior of the Chebyshev–Halley methods on the family of degree n polynomials z n + c . We prove that, despite increasing the degree, it is still possible to draw the parameter space by using the orbit of a single critical point. For the methods having z = ∞ as an attracting fixed point, we show how the basins of attraction of the roots become smaller as the value of n grows. We also demonstrate that, although the convergence order of the Chebyshev–Halley family is 3, there is a member of order 4 for each value of n. In the case of quadratic polynomials, we bound the set of parameters which correspond to iterative methods with stable behaviour other than the basins of attraction of the roots.
Published: 2018

31. Prioritized Norms in Formal Argumentation

Author: Serena Villata, Beishui Liao, Nir Oren, Leendert van der Torre, Zhejiang University, University of Aberdeen, Individual and Collective Reasoning (ICR), University of Luxembourg [Luxembourg], Web-Instrumented Man-Machine Interactions, Communities and Semantics (WIMMICS), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Scalable and Pervasive softwARe and Knowledge Systems (Laboratoire I3S - SPARKS), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), Centre National de la Recherche Scientifique (CNRS), The research reported in this paper was partially supported by the Fundamental Research Funds for the Central Universities of China for the project Big Data, Reasoning and Decision Making, the National Research Fund Luxembourg (FNR) under grant INTER/MOBILITY/14/8813732 for the project FMUAT: Formal Models for Uncertain Argumentation from Text, and the European Union’s Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No 690974 for the project MIREL: MIning and REasoning with Legal texts., and European Project: 690974,H2020 Pilier Excellent Science,H2020-MSCA-RISE-2015,MIREL(2016)
Subjects: FOS: Computer and information sciences, Logic, Computer Science - Artificial Intelligence, Big data, [SCCO.COMP]Cognitive science/Computer science, 0102 computer and information sciences, normative multiagent systems, 01 natural sciences, ComputingMethodologies_ARTIFICIALINTELLIGENCE, Theoretical Computer Science, Argumentation theory, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], Arts and Humanities (miscellaneous), normative systems, media_common.cataloged_instance, European commission, European union, China, Mathematics, media_common, deontic logic, Computer science [C05] [Engineering, computing & technology], business.industry, Deontic logic, Public relations, Sciences informatiques [C05] [Ingénierie, informatique & technologie], 16. Peace & justice, TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, Artificial Intelligence (cs.AI), 010201 computation theory & mathematics, Hardware and Architecture, Normative systems, business, formal argumentation, Social psychology, norms, Software
Abstract: To resolve conflicts among norms, various nonmonotonic formalisms can be used to perform prioritized normative reasoning. Meanwhile, formal argumentation provides a way to represent nonmonotonic logics. In this paper, we propose a representation of prioritized normative reasoning by argumentation. Using hierarchical abstract normative systems, we define three kinds of prioritized normative reasoning approaches, called Greedy, Reduction, and Optimization. Then, after formulating an argumentation theory for a hierarchical abstract normative system, we show that for a totally ordered hierarchical abstract normative system, Greedy and Reduction can be represented in argumentation by applying the weakest link and the last link principles respectively, and Optimization can be represented by introducing additional defeats capturing the idea that for each argument that contains a norm not belonging to the maximal obeyable set then this argument should be rejected., Accepted by the Journal of Logic and Computation on November 2nd, 2017
Published: 2017

32. Extreme Value Laws for non stationary processes generated by sequential and random dynamical systems

Author: Ana C. Freitas, Sandro Vaienti, Jorge Milhazes Freitas, Centro de Matemática - Universidade do Porto (CMUP), Universidade do Porto = University of Porto, Centre de Physique Théorique - UMR 7332 (CPT), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), CPT - Ex E7 Systèmes dynamiques et théorie ergodique, Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), ACMF was partially supported by FCT (Portugal) grant SFRH/BPD/66174/2009. JMF was partially supported by FCT grant SFRH/BPD/66040/2009. All these grants are financially supported by the program POPH/FSE. ACMF and JMF were partially supported by FCT project FAPESP/19805/2014 and by CMUP (UID/MAT/00144/2013), which is funded by FCT with national (MEC) and European structural funds through the programs ,FEDER, under the partnership agreement PT2020. SV was supported by the ANRProject Perturbations and by the project Atracción de Capital Humano Avanzado del Extranjero MEC 80130047, CONICYT, at the CIMFAV, University of Valparaiso. All authors were partially supported by FCT project PTDC/MAT/12034 /2010, which is funded by national and European structural funds through the programs FEDER and COMPETE. SV is grateful to N. Haydn, M. Nicol and A. Török for several and fruitful discussions on sequential systems, especially in the framework of indifferent maps. JMF is grateful to M. Todd for fruitful discussions and careful reading of a preliminary version of this paper. All authors acknowledge the Isaac Newton Institute for Mathematical Sciences, where this work was initiated during the program Mathematics for the Fluid Earth., ANR-10-BLAN-0106,PERTURBATIONS,Perturbations aléatoires de systèmes dynamiques: applications non-uniformément dilatantes, isométries, billards et systèmes de fonctions itérées. Grandes déviations et valeurs extrêmes.(2010), Faculdade de Economia, Faculdade de Ciências, and Universidade do Porto
Subjects: Hitting Times, Statistics and Probability, Pure mathematics, Random dynamical systems, 60G70, [MATH.MATH-DS]Mathematics [math]/Dynamical Systems [math.DS], FOS: Physical sciences, Dynamical Systems (math.DS), 01 natural sciences, 010104 statistics & probability, Sequential dynamical systems, FOS: Mathematics, 37A50, Mathematics - Dynamical Systems, 0101 mathematics, Extreme value theory, Mathematical Physics, Mathematics, 37A25, 37B20, Non-stationarity, Probability (math.PR), 010102 general mathematics, Mathematical Physics (math-ph), Non stationarity, Statistics, Probability and Uncertainty, Mathematics - Probability
Abstract: International audience; We develop and generalize the theory of extreme value for non-stationary stochastic processes, mostly by weakening the uniform mixing condition that was previously used in this setting. We apply our results to non-autonomous dynamical systems, in particular to sequential dynamical systems, both given by uniformly expanding maps and by maps with a neutral fixed point, and to a few classes of random dynamical systems. Some examples are presented and worked out in detail.
Published: 2017

33. Observer design for linear singular time-delay systems

Author: Francisco Javier Bejarano, Gang Zheng, Non-Asymptotic estimation for online systems (NON-A), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Escuela Superior de Ingeniería Mecánica y Eléctrica - Unidad Profesional Ticomán (ESIME-UPT), Instituto Politecnico Nacional [Mexico] (IPN), This paper was supported in part by Ministry of Higher Education and Research Nord-Pas de Calais Regional Council, by FEDER through the Contrat de Projets Etat Region (CPER), by ARCIR Project ESTIREZ Nord-Pas de Calais Regional Council. F.J. Bejarnano acknowledges as well the support of Proyecto SIP 20161492, Mexico., Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: commensurate delays, 0209 industrial biotechnology, Class (set theory), Time delays, Observer (quantum physics), Existential quantification, observer, 02 engineering and technology, State (functional analysis), Delayed singular systems, 020901 industrial engineering & automation, Control and Systems Engineering, Control theory, [INFO.INFO-AU]Computer Science [cs]/Automatic Control Engineering, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, State observer, Electrical and Electronic Engineering, Mathematics
Abstract: International audience; This paper investigates the problem of observer design for a general class of linear singular time-delay systems, in which the time delays are involved in the state and its derivatives, the output and the known input (if there exists). The involvement of the delay could be multiple which however is rarely studied in the literature. Sufficient conditions are proposed which guarantees the existence of a Luenberger-like observer for the general system.
Published: 2017

34. Forms of differing degrees over number fields

Author: Christopher Frei, Manfred G. Madritsch, Institut für Analysis und Computational Number Theory (Technische Universität Graz), Institut Élie Cartan de Lorraine (IECL), Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), and For the realization of the present paper the second author received support from the Conseil Régional de Lorraine.
Subjects: Pure mathematics, Conjecture, Mathematics - Number Theory, Degree (graph theory), 11G35, 11P55, 14G05, General Mathematics, 010102 general mathematics, System of polynomial equations, Singular integral, Algebraic number field, 01 natural sciences, Ring of integers, [MATH.MATH-NT]Mathematics [math]/Number Theory [math.NT], Hasse principle, 0103 physical sciences, FOS: Mathematics, Asymptotic formula, Number Theory (math.NT), 010307 mathematical physics, 0101 mathematics, Mathematics
Abstract: Consider a system of polynomials in many variables over the ring of integers of a number field $K$. We prove an asymptotic formula for the number of integral zeros of this system in homogeneously expanding boxes. As a consequence, any smooth and geometrically integral variety $X\subseteq \mathbb{P}_K^m$ satisfies the Hasse principle, weak approximation and the Manin-Peyre conjecture, if only its dimension is large enough compared to its degree. This generalizes work of Skinner, who considered the case where all polynomials have the same degree, and recent work of Browning and Heath-Brown, who considered the case where $K=\mathbb{Q}$. Our main tool is Skinner's number field version of the Hardy-Littlewood circle method. As a by-product, we point out and correct an error in Skinner's treatment of the singular integral., Comment: 23 pages; minor revision; to appear in Mathematika
Published: 2017

35. Multi-dimensional signal approximation with sparse structured priors using split Bregman iterations

Author: Michèle Sebag, Cédric Gouy-Pailler, Yoann Isaac, Quentin Barthélemy, Jamal Atif, Laboratoire d'analyse des données et d'intelligence des systèmes (LADIS), Département Métrologie Instrumentation & Information (DM2I), Laboratoire d'Intégration des Systèmes et des Technologies (LIST), Direction de Recherche Technologique (CEA) (DRT (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Direction de Recherche Technologique (CEA) (DRT (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Université Paris-Saclay-Laboratoire d'Intégration des Systèmes et des Technologies (LIST), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Université Paris-Saclay, TAckling the Underspecified (TAU), Laboratoire de Recherche en Informatique (LRI), Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Mensia Technologies [Rennes], Mensia Technologies [Paris], Université Paris-Sud - Paris 11 (UP11)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS), The work presented in this paper has been partially funded by DIGITEO under the Grant 2011-053D, Laboratoire d'Intégration des Systèmes et des Technologies (LIST (CEA)), Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Commissariat à l'énergie atomique et aux énergies alternatives (CEA)-Université Paris-Saclay-Laboratoire d'Intégration des Systèmes et des Technologies (LIST (CEA)), CentraleSupélec-Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS)-CentraleSupélec-Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, and CentraleSupélec-Université Paris-Sud - Paris 11 (UP11)-Centre National de la Recherche Scientifique (CNRS)
Subjects: FOS: Computer and information sciences, Signal processing, Optimization problem, Noise reduction, Computer Vision and Pattern Recognition (cs.CV), Computer Science - Computer Vision and Pattern Recognition, 02 engineering and technology, Machine Learning (cs.LG), [INFO.INFO-TS]Computer Science [cs]/Signal and Image Processing, Recovery, Computer Science - Data Structures and Algorithms, Prior probability, Regularization, 0202 electrical engineering, electronic engineering, information engineering, Data Structures and Algorithms (cs.DS), Electrical and Electronic Engineering, Selection, Image restoration, Mathematics, business.industry, Linear Inverse Problems, 020206 networking & telecommunications, Pattern recognition, Sparse approximation, [INFO.INFO-NA]Computer Science [cs]/Numerical Analysis [cs.NA], Regression, Minimization, Computer Science - Learning, Image-Restoration, Control and Systems Engineering, Statistical analysis, 020201 artificial intelligence & image processing, [SDV.NEU]Life Sciences [q-bio]/Neurons and Cognition [q-bio.NC], Computer Vision and Pattern Recognition, Decomposition method (constraint satisfaction), Artificial intelligence, Minification, Lasso, business, Software, Algorithms, [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA]
Abstract: This paper addresses the structurally constrained sparse decomposition of multi-dimensional signals onto overcomplete families of vectors, called dictionaries. The contribution of the paper is threefold. Firstly, a generic spatio-temporal regularization term is designed and used together with the standard ź 1 regularization term to enforce a sparse decomposition preserving the spatio-temporal structure of the signal. Secondly, an optimization algorithm based on the split Bregman approach is proposed to handle the associated optimization problem, and its convergence is analyzed. Our well-founded approach yields same accuracy as the other algorithms at the state of the art, with significant gains in terms of convergence speed. Thirdly, the empirical validation of the approach on artificial and real-world problems demonstrates the generality and effectiveness of the method. On artificial problems, the proposed regularization subsumes the Total Variation minimization and recovers the expected decomposition. On the real-world problem of electro-encephalography brainwave decomposition, the approach outperforms similar approaches in terms of P300 evoked potentials detection, using structured spatial priors to guide the decomposition. HighlightsA sparse structured decomposition method is proposed for multi-dimensional signals.Knowledge priors are encoded in a regularization to obtain plausible representations.The proposed split-Bregman based method outperforms counterparts in terms of speed.The approach is applied to EEG denoising for the extraction of P300 potentials.
Published: 2017

36. Various approaches for the study of the complexity of some families of pseudorandom subsets

Author: Domingo Gómez-Pérez, Cécile Dartyge, Institut Élie Cartan de Lorraine (IECL), Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Universidad de Cantabria [Santander], During the preparation of this paper the second author was par-tially supported by project MTM2014-55421-P from the Ministerio de Economia y Competitividad, and ANR-14-CE34-0009,MuDeRa,Multiplicativity, determinism, and Randomness(2014)
Subjects: Discrete mathematics, Pseudorandom number generator, Combinatorics, Development (topology), Geometry of numbers, General Mathematics, Discrete geometry, Pseudorandomness, complexity, Randomness, [MATH.MATH-NT]Mathematics [math]/Number Theory [math.NT], Mathematics
Abstract: International audience; Studying randomness in different structures is important from the development of applications and theory. Dartyge, Mosaki and Sárközy (among others) have studied measures of randomness for families of subsets of integers. In this article, we improve results on the complexity of some families defined by polynomials, introducing new techniques from areas such us combinatorial geometry, geometry of numbers and additive combinatorics.
Published: 2017

37. Maximum Distortion Attacks in Electricity Grids

Author: H. Vincent Poor, Oliver Kosut, Inaki Esnaola, Samir M. Perlaza, University of Sheffield [Sheffield], Software and Cognitive radio for telecommunications (SOCRATE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-CITI Centre of Innovation in Telecommunications and Integration of services (CITI), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA), Princeton University, Arizona State University [Tempe] (ASU), This work was supported in part by the European Commission under Individual Fellowship Marie Skłodowska-CurieAction (CYBERNETS) under Grant 659316, and in part by the U.S. National Science Foundation under Grant CMMI-1435778 and Grant ECCS-1549881. Paper no. TSG-01065-2015., European Project: 659316,H2020 Pilier Excellent Science,H2020-MSCA-IF-2014,CYBERNETS(2015), Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), and Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon
Subjects: game theory, State variable, Mathematical optimization, Data-injection attacks, General Computer Science, Exploit, MMSE estimation, 020209 energy, [MATH.MATH-IT]Mathematics [math]/Information Theory [math.IT], 020206 networking & telecommunications, 02 engineering and technology, symbols.namesake, Cardinality, de-centralized attacks, [INFO.INFO-TS]Computer Science [cs]/Signal and Image Processing, Nash equilibrium, Distortion, 0202 electrical engineering, electronic engineering, information engineering, symbols, Potential game, Game theory, Gaussian process, Mathematics, Computer Science::Cryptography and Security
Abstract: International audience; Multiple attacker data injection attack construction in electricity grids with minimum-mean-square-error state estimation is studied for centralized and decentralized scenarios. A performance analysis of the trade-off between the maximum distortion that an attack can introduce and the probability of the attack being detected by the network operator is considered. In this setting, optimal centralized attack construction strategies are studied. The decentralized case is examined in a game-theoretic setting. A novel utility function is proposed to model this trade-off and it is shown that the resulting game is a potential game. The existence and cardinality of the corresponding set of Nash Equilibria (NEs) of the game is analyzed. Interestingly, the attackers can exploit the correlation among the state variables to facilitate the attack construction. It is shown that attackers can agree on a data injection vector construction that achieves the best trade-off between distortion and detection probability by sharing only a limited number of bits offlline. For the particular case of two attackers, numerical results based on IEEE test systems are presented.
Published: 2016

38. Design of interval observer for a class of uncertain unobservable nonlinear systems

Author: Denis Efimov, Wilfrid Perruquetti, Gang Zheng, Non-Asymptotic estimation for online systems (NON-A), Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), This paper was supported in part by Ministry of Higher Education and Research Nord-Pas de Calais Regional Council, by FEDER through the Contrat de Projets Etat Region (CPER), by ARCIR Project ESTIREZ Nord-Pas de Calais Regional Council, by the Government of Russian Federation (Grant 074-U01) and the Ministry of Education and Science of Russian Federation (Project 14.Z50.31.0031)., Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), and Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)
Subjects: 0209 industrial biotechnology, Observer (quantum physics), 020208 electrical & electronic engineering, Observable, 02 engineering and technology, Interval (mathematics), 16. Peace & justice, Lipschitz continuity, Unobservable, Nonlinear system, Superposition principle, 020901 industrial engineering & automation, Control and Systems Engineering, Control theory, [INFO.INFO-AU]Computer Science [cs]/Automatic Control Engineering, 0202 electrical engineering, electronic engineering, information engineering, State observer, Electrical and Electronic Engineering, Mathematics
Abstract: International audience; This paper investigates the interval observer design for a class of nonlinear continuous systems, which can be represented as a superposition of a uniformly observable nominal subsystem with a Lipschitz nonlinear perturbation. It is shown in this case there exists an interval observer for the system that estimates the set of admissible values for the state consistent with the output measurements. An illustrative example of the observer application is given with simulation results.
Published: 2016

39. Derandomizing random walks in undirected graphs using locally fair exploration strategies

Author: Ralf Klasing, Adrian Kosowski, Colin Cooper, David Ilcinkas, Department of Computer Science (DCS), King‘s College London, Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Combinatoire et Algorithmique, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), See paper for details., ANR-07-BLAN-0322,ALADDIN,Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks(2007), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Department of Algorithms and Systems Modelling [ETI GUT] (Gdansk University of Technology), Faculty of Electronics, Telecommunications and Informatics [GUT Gdańsk] (ETI), Gdańsk University of Technology (GUT)-Gdańsk University of Technology (GUT), ANR-05-MMSA-0006,ALPAGE,ALgorithmique des Plates-formes A Grande Echelle(2005), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), and Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Mathematical optimization, Computer Networks and Communications, Computer science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Comparability graph, Random walk, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, law.invention, Theoretical Computer Science, Combinatorics, Indifference graph, Graph exploration, law, Graph power, Line graph, Random regular graph, 0202 electrical engineering, electronic engineering, information engineering, Pancyclic graph, Mathematics, Discrete mathematics, Block graph, graph exploration : Propp machine, Directed graph, Feedback arc set, Computational Theory and Mathematics, 010201 computation theory & mathematics, Hardware and Architecture, Robbins' theorem, Graph (abstract data type), 020201 artificial intelligence & image processing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: International audience; We consider the problem of exploring an anonymous undirected graph using an oblivious robot. The studied exploration strategies are designed so that the next edge in the robot's walk is chosen using only local information, and so that some local equity (fairness) criterion is satisfied for the adjacent undirected edges. Such strategies can be seen as an attempt to derandomize random walks, and are natural counterparts for undirected graphs of the rotor-router model for symmetric directed graphs. The first of the studied strategies, known as Oldest-First (OF), always chooses the neighboring edge for which the most time has elapsed since its last traversal. Unlike in the case of symmetric directed graphs, we show that such a strategy in some cases leads to exponential cover time. We then consider another strategy called Least-Used-First (LUF) which always uses adjacent edges which have been traversed the smallest number of times. We show that any Least-Used-First exploration covers a graph G=(V,E) of diameter diam within time O(diam|E|), and in the long run traverses all edges of G with the same frequency.
Published: 2011

40. Remembering without memory: Tree exploration by asynchronous oblivious robots

Author: Nicola Santoro, David Ilcinkas, Andrzej Pelc, Paola Flocchini, Distributed Computing Research Group [Ottawa], University of Ottawa [Ottawa], Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Département d'Informatique et d'Ingénierie (DII), Université du Québec en Outaouais (UQO), School of Computer Science [Ottawa], Carleton University, See paper for details., ANR-07-BLAN-0322,ALADDIN,Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks(2007), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Partially supported by NSERC Discovery grant. Andrzej Pelc is also partially supported by the Research Chair in Distributed Computing at the Université du Québec en Outaouais. This work was done during the stay of David Ilcinkas at the Research Chair in Distributed Computing of the Université du Québec en Outaouais and at the University of Ottawa, as a postdoctoral fellow., and Alexander A. Shvartsman, Pascal Felber
Subjects: Theoretical computer science, General Computer Science, Computer science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, exploration, 01 natural sciences, Constructive, Theoretical Computer Science, Combinatorics, Computer Science::Robotics, oblivious, mobile agent, 0202 electrical engineering, electronic engineering, information engineering, Mathematics, asynchronous, Discrete mathematics, Degree (graph theory), Swarm behaviour, robot, Mobile robot, Binary logarithm, tree, Asymptotically optimal algorithm, 010201 computation theory & mathematics, Asynchronous communication, Robot, Graph (abstract data type), 020201 artificial intelligence & image processing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Computer Science(all)
Abstract: International audience; In the effort to understand the algorithmic limitations of computing by a swarm of robots, the research has focused on the minimal capabilities that allow a problem to be solved. The weakest of the commonly used models is {\sc Asynch} where the autonomous mobile robots, endowed with visibility sensors (but otherwise unable to communicate), operate in Look-Compute-Move cycles performed asynchronously for each robot. The robots are often assumed (or required to be) oblivious: they keep no memory of observations and computations made in previous cycles. We consider the setting when the robots are dispersed in an anonymous and unlabeled graph, and they must perform the very basic task of {\em exploration}: within finite time every node must be visited by at least one robot and the robots must enter a quiescent state. The complexity measure of a solution is the number of robots used to perform the task. We study the case when the graph is an arbitrary tree and establish some unexpected results. We first prove that, in general, exploration cannot be done efficiently. More precisely we prove that there are $n$-node trees where $\Omega(n)$ robots are necessary; this holds even if the maximum degree is $4$. On the other hand, we show that if the maximum degree is $3$, it is possible to explore with only $O(\frac{\log n} {\log\log n})$ robots. The proof of the result is constructive. We also prove that the size of the team used in our solution is asymptotically {\em optimal}: there are trees of degree $3$, whose exploration requires $\Omega(\frac{\log n}{\log\log n})$ robots. Our final result shows that the difficulty in tree exploration comes in fact from the symmetries of the tree. Indeed, we show that, in order to explore trees that do not have any non-trivial automorphisms, 4 robots are always sufficient and often necessary.
Published: 2010

41. Classification Models Via Tabu Search: An Application to Early Stage Venture Classification

Author: Canan Akdemir, Thomas B. Astebro, Samir Elhedhli, Department of Management Sciences, University of Waterloo [Waterloo], Joseph L. Rotman School of Management, University of Toronto, HEC Research Paper Series, Haldemann, Antoine, Groupement de Recherche et d'Etudes en Gestion à HEC (GREGH), and Ecole des Hautes Etudes Commerciales (HEC Paris)-Centre National de la Recherche Scientifique (CNRS)
Subjects: JEL: C - Mathematical and Quantitative Methods/C.C5 - Econometric Modeling/C.C5.C53 - Forecasting and Prediction Methods • Simulation Methods, Mixed integer program, Computer science, media_common.quotation_subject, Benders' decomposition, Machine learning, computer.software_genre, decision heuristic, JEL: C - Mathematical and Quantitative Methods/C.C4 - Econometric and Statistical Methods: Special Topics/C.C4.C45 - Neural Networks and Related Topics, JEL: C - Mathematical and Quantitative Methods/C.C6 - Mathematical Methods • Programming Models • Mathematical and Simulation Modeling/C.C6.C63 - Computational Techniques • Simulation Modeling, Artificial Intelligence, Classification models, tabu search, Quality (business), Decision-making, Selection (genetic algorithm), media_common, Mathematics, business.industry, General Engineering, early stage venture forecast, large-scale mixed integer program, Tabu search, Computer Science Applications, Data set, classification, [SHS.GESTION.STRAT]Humanities and Social Sciences/Business administration/domain_shs.gestion.strat, [SHS.GESTION]Humanities and Social Sciences/Business administration, Stage (hydrology), Data mining, Artificial intelligence, [SHS.GESTION] Humanities and Social Sciences/Business administration, business, computer, Integer (computer science)
Abstract: We model the decision making process used by Experts at the Canadian Innovation Centre to classify early stage venture proposals based on potential commercial success. The decision is based on thirty-seven attributes that take values in { - 1 , 0 , 1 } . We adopt a conjunctive decision framework due to Astebro and Elhedhli (2005) that selects a subset of attributes and determines two threshold values: one for the maximum allowed negatives (n) and one for minimum required positives (p). A proposal is classified as a success if the number of positives is greater than or equal to p and the number of negatives is less than or equal to n over the selected attributes. Based on a data set of 561 observations, the selection of attributes and the determination of the threshold values is modeled as a large-scale mixed integer program. Two solution approaches are explored: Benders decomposition and Tabu search. The first, was very slow to converge, while the second provided high quality solutions quickly. Tabu search provides excellent classification accuracy for predicting commercial successes as well as replicating Experts’ forecasts, opening the venue for the use of Tabu search in scoring and classification problems.
Published: 2015

42. Beachcombing on Strips and Islands

Author: Evangelos Bampas, David Ilcinkas, Jurek Czyzowicz, Ralf Klasing, Laboratoire d'Informatique et Systèmes (LIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), Département d'Informatique et d'Ingénierie (DII), Université du Québec en Outaouais (UQO), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), ANR-11-BS02-0014,DISPLEXITY,Calculabilité et complexité en distribué(2011), ANR-10-IDEX-0003,IDEX BORDEAUX,Initiative d'excellence de l'Université de Bordeaux(2010), See paper for details., and Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Discrete mathematics, Conjecture, General Computer Science, Competitive analysis, Computer science, Generalization, Approximation algorithm, Mobile robot, 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Infimum and supremum, Domain (mathematical analysis), Theoretical Computer Science, Preferred walking speed, Combinatorics, 010201 computation theory & mathematics, Line (geometry), 0202 electrical engineering, electronic engineering, information engineering, Robot, Point (geometry), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Online algorithm, Mathematics
Abstract: International audience; A group of mobile robots (beachcombers) have to search collectively every point of a given domain. At any given moment, each robot can be in {\em walking mode} or in {\em searching mode}. It is assumed that each robot's maximum allowed searching speed is strictly smaller than its maximum allowed walking speed. A point of the domain is searched if at least one of the robots visits it in searching mode. The Beachcombers' Problem consists in developing efficient {\em schedules} (algorithms) for the robots which collectively search all the points of the given domain as fast as possible. We consider searching schedules in the following one-dimensional geometric domains: the cycle of a known circumference $L$, the finite straight line segment of a known length $L$, and the semi-infinite line $[0,+\infty)$.We first consider the {\em online} Beachcombers' Problem (i.e.~the scenario when the robots do not know in advance the length of the segment to be searched), where the robots are initially collocated at the origin of a semi-infinite line. It is sought to design a schedule $A$ with maximum {\em speed} $S$, defined as $S = \inf_{\ell}{\frac{\ell}{t_A(\ell)}}$, where $t_A(\ell)$ denotes the time when the search of the segment $[0,\ell]$ is completed under $A$. We consider a {\em discrete} and a {\em continuous} version of the problem, depending on whether the infimum is takenover $\ell \in \mathbb{N}^*$ or $\ell \geq 1$. We prove that the $\mathtt{LeapFrog}$ algorithm, which was proposed in [Czyzowicz et al., SIROCCO 2014, LNCS 8576, pp. 23--36 (2014)], is in fact optimal in the discrete case. This settles in the affirmative a conjecture from that paper. We also show how to extend this result to the more general continuous online setting.For the {\em offline} version of the Beachcombers' Problem (i.e.~the scenario when the robots know in advance the length of the segment to be searched), we consider the \emph{$t$-source} Beachcombers' Problem (i.e.~all robots start from a fixed number $t \geq 1$ of starting positions) on the cycle and on the finite segment. For the \emph{$t$-source} Beachcombers' Problem on the cycle, we show that the structure of the optimal solutions is identical to the structure of the optimal solutions to the $2t$-source Beachcombers' Problem on a finite segment. In consequence, by using results from [Czyzowicz et al., ALGOSENSORS 2014, LNCS 8847, pp.~3--21 (2014)], we prove that the \emph{1-source} Beachcombers' Problem on the cycle is NP-hard, and we derive approximation algorithms for the problem. For the \emph{$t$-source} variant of the Beachcombers' Problem on the cycle and on the finite segment, we also derive efficient approximation algorithms.One important contribution of our work is that, in all variants of the offline Beachcombers' Problem that we discuss, we allow the robots to \emph{change direction of movement} and search points of the domain on both sides of their respective starting positions. This represents a significant generalization compared to the model considered in~[Czyzowicz et al., ALGOSENSORS 2014, LNCS 8847, pp. 3--21 (2014)], in which each robot had a fixed direction of movement that was specified as part of the solution to the problem. We manage to prove that changes of direction do not help the robots achieve optimality.
Published: 2015

43. Comparisons of Ambiguous Experiments

Author: Ludovic Renou, Fabien Gensbittel, Tristan Tomala, Haldemann, Antoine, Groupe de recherche en économie mathématique et quantitative (GREMAQ), Centre National de la Recherche Scientifique (CNRS)-École des hautes études en sciences sociales (EHESS)-Institut National de la Recherche Agronomique (INRA)-Université Toulouse 1 Capitole (UT1), University of Essex, Groupement de Recherche et d'Etudes en Gestion à HEC (GREGH), Ecole des Hautes Etudes Commerciales (HEC Paris)-Centre National de la Recherche Scientifique (CNRS), HEC Research Paper Series, and Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées
Subjects: Mathematical optimization, media_common.quotation_subject, 05 social sciences, Ambiguity, experiments, Decision maker, Minimax, value of information, Value of information, maximin, Set (abstract data type), multiple priors, Joint probability distribution, 0502 economics and business, JEL: C - Mathematical and Quantitative Methods/C.C7 - Game Theory and Bargaining Theory/C.C7.C72 - Noncooperative Games, [SHS.GESTION]Humanities and Social Sciences/Business administration, Point (geometry), rectangularity, 050207 economics, [SHS.GESTION] Humanities and Social Sciences/Business administration, 050205 econometrics, media_common, Mathematics
Abstract: An ambiguous statistical experiment is a set of joint probability distributions over states and signals. This note compares ambiguous experiments from the point of view of an ambiguity averse decision maker and extends the Blackwell (1951, 1953) ordering to this setting.
Published: 2015

44. Judgment Aggregation Theory Can Entail New Social Choice Results

Author: Philippe Mongin, François Maniquet, Haldemann, Antoine, Center of Operation Research and Econometrics [Louvain] (CORE), Université Catholique de Louvain = Catholic University of Louvain (UCL), Groupement de Recherche et d'Etudes en Gestion à HEC (GREGH), Ecole des Hautes Etudes Commerciales (HEC Paris)-Centre National de la Recherche Scientifique (CNRS), HEC Paris Research Paper Series, and UCL - SSH/IMMAQ/CORE - Center for operations research and econometrics
Subjects: aggregation of classifications, Judgement, social choice, Social choice, jel:C65, Aggregation of classifications, logical aggregation, 0502 economics and business, Assignments, Judgment aggregation, Logical aggregation, Nonbinary evaluations, 050207 economics, Mathematics, social choice, judgment aggregation, logical aggregation, aggregation of classifications, assignments, nonbinary evaluations, Management science, Field (Bourdieu), assignments, 05 social sciences, jel:D71, JEL: D - Microeconomics/D.D7 - Analysis of Collective Decision-Making/D.D7.D71 - Social Choice • Clubs • Committees • Associations, nonbinary evaluations, JEL: C - Mathematical and Quantitative Methods/C.C6 - Mathematical Methods • Programming Models • Mathematical and Simulation Modeling/C.C6.C65 - Miscellaneous Mathematical Tools, Focus (linguistics), judgment aggregation, [SHS.GESTION]Humanities and Social Sciences/Business administration, 050206 economic theory, [SHS.GESTION] Humanities and Social Sciences/Business administration, Mathematical economics, Social choice theory
Abstract: Judgment (or logical) aggregation theory is logically more powerful than social choice theory and has been put to use to recover some classic results of this field. Whether it could also enrich it with genuinely new results is still controversial. To support a positive answer, the authors prove a social choice theorem by using the advanced nonbinary form of judgment aggregation theory developed by Dokow and Holzman (2010c). This application involves aggregating classifications (specifically assignments) instead of preferences, and this focus justifies shifting away from the binary framework of standard judgement aggregation theory to a more general one.
Published: 2014

45. Comments on Finite-time Stability of Time-Delay Systems

Author: Denis Efimov, Jean-Pierre Richard, Andrey Polyakov, Wilfrid Perruquetti, Emilia Fridman, Non-Asymptotic estimation for online systems (NON-A), Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Systèmes Non Linéaires et à Retards (SyNeR), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Department of Electrical Engineering, Tel Aviv University [Tel Aviv], This work was partially supported by the Government of Russian Federation (Grant 074-U01), the Ministry of Education and Science of Russian Federation (Project 14.Z50.31.0031) and by Israel Science Foundation (Grant No. 754/10). The material in this paper was not presented at any conference., Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), and Tel Aviv University (TAU)
Subjects: Control and Systems Engineering, Control theory, [INFO.INFO-AU]Computer Science [cs]/Automatic Control Engineering, Convergence (routing), Stability (learning theory), Electrical and Electronic Engineering, Finite time, Mathematics, [SPI.AUTO]Engineering Sciences [physics]/Automatic
Abstract: International audience; Recently proposed conditions on finite-time stability in time-delay systems are revisited and it is shown that they are incorrect. General comments on possibility of finite-time convergence in time-delay systems and a necessary condition are given.
Published: 2014

46. Distributedly Testing Cycle-Freeness

Author: Pierre Fraigniaud, Fabien Mathieu, Heger Arfaoui, David Ilcinkas, Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Networks, Graphs and Algorithms (GANG), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)-Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Laboratory of Information, Network and Communication Sciences (LINCS), Université Pierre et Marie Curie - Paris 6 (UPMC)-Institut National de Recherche en Informatique et en Automatique (Inria)-Institut Mines-Télécom [Paris] (IMT), Alcatel Lucent Bell Labs, ALCATEL, See paper for details., ANR-11-BS02-0014,DISPLEXITY,Calculabilité et complexité en distribué(2011), and Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)
Subjects: [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Central authority, Theoretical computer science, Property (programming), Node (networking), Free group, Distributed testing, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Appropriate use, Graph property, Wireless sensor network, Mathematics
Abstract: International audience; We tackle \emph{local distributed testing} of graph properties. This framework is well suited to contexts in which data dispersed among the nodes of a network can be collected by some central authority (like in, e.g., sensor networks). In local distributed testing, each node can provide the central authority with just a few information about what it perceives from its neighboring environment, and, based on the collected information, the central authority is aiming at deciding whether or not the network satisfies some property. We analyze in depth the prominent example of checking \emph{cycle-freeness}, and establish tight bounds on the amount of information to be transferred by each node to the central authority for deciding cycle-freeness. In particular, we show that distributedly testing cycle-freeness requires at least $\lceil{\log d}\rceil-1$ bits of information per node in graphs with maximum degree~$d$, even for connected graphs. Our proof is based on a novel version of the seminal result by Naor and Stockmeyer (1995) enabling to reduce the study of certain kinds of algorithms to order-invariant algorithms, and on an appropriate use of the known fact that every free group can be linearly ordered.
Published: 2014

47. Use of Two-Part Regression Calibration Model to Correct for Measurement Error in Episodically Consumed Foods in a Single-Replicate Study Design: EPIC Case Study

Author: Agogo, George O, der Voet, Hilko van, Veer, Pieter Van't, Ferrari, Pietro, Leenders, Max, Muller, David C, Sánchez-Cantalejo, Emilio, Bamia, Christina, Braaten, Tonje, Knüppel, Sven, Johansson, Ingegerd, van Eeuwijk, Fred A, Boshuizen, Hendriek, LS IRAS EEPI GRA (Gezh.risico-analyse), IRAS RATIA-SIB, Risk Assessment of Toxic and Immunomodulatory Agents, [Agogo,GO, Boshuizen,H] National Institute for Public Health and the Environment, Bilthoven, The Netherlands. [Agogo,GO, Voet,HV, Eeuwijk,FAV, Boshuizen,H] Biometris, Wageningen University and Research Center, Wageningen, The Netherlands.[Veer,PV, Boshuizen,H] Department of Human Nutrition, Wageningen University and Research Center, Wageningen, The Netherlands. [Ferrari,P] Nutritional Epidemiology Group, International Agency for Research on Cancer, Lyon, France. [Leenders,M] Department of Gastroenterology and Hepatology, University Medical Center Utrecht, Utrecht, The Netherlands. [Muller,DC] Genetic Epidemiology Group, International Agency for Research on Cancer, Lyon, France. [Sánchez-Cantalejo,E] Andalusian School of Public Health, Granada, Spain. CIBER de Epidemiología y Salud Pública (CIBERESP), Barcelona, Spain. [Bamia,C] WHO Collaborating Center for Food and Nutrition Policies, Department of Hygiene, Epidemiology and Medical Statistics, University of Athens Medical School, Athens, Greece. [Braaten,T] Department of Community Medicine, University of Tromsø, Tromsø, Norway. [Knüppel,S] Department of Epidemiology, German Institute of Human Nutrition Potsdam-Rehbrücke, Potsdam, Germany. [Johansson,I] Department of Odontology, Umea University, Umea, Sweden., However, the publication cost will be covered by Wageningen University and Research Centre, Biometris, P.O. Box 100, 6700 AC WAGENINGEN should the paper be accepted for a publication., LS IRAS EEPI GRA (Gezh.risico-analyse), IRAS RATIA-SIB, and Risk Assessment of Toxic and Immunomodulatory Agents
Subjects: Male, Parametric Analysis, Medicin och hälsovetenskap, Nutrition and Disease, Calibration (statistics), Test Statistics, lcsh:Medicine, markers, Overfitting, Statistical Inference, outcomes, Medical and Health Sciences, Wiskundige en Statistische Methoden - Biometris, Mathematical and Statistical Techniques, Neoplasms, Surveys and Questionnaires, Voeding en Ziekte, Statistics, Medicine, Prospective Studies, lcsh:Science, Multidisciplinary, Maximum Likelihood Estimation, Regression analysis, Estudios Prospectivos, Replicate, Diseases::Neoplasms [Medical Subject Headings], Middle Aged, PE&RC, Neoplasias, Diet Records, Europe, Survival Rate, Biometris, nutrition, Physical Sciences, Calibration, instruments, Regression Analysis, Dieta, Female, dietary self-report, Statistics (Mathematics), Bayesian Statistics, Research Article, Adult, Heteroscedasticity, Analytical, Diagnostic and Therapeutic Techniques and Equipment::Investigative Techniques::Epidemiologic Methods::Epidemiologic Study Characteristics as Topic::Epidemiologic Studies::Cohort Studies::Longitudinal Studies::Prospective Studies [Medical Subject Headings], General Science & Technology, Logit, Phenomena and Processes::Physiological Phenomena::Nutritional Physiological Phenomena::Diet [Medical Subject Headings], Research and Analysis Methods, Analytical, Diagnostic and Therapeutic Techniques and Equipment::Investigative Techniques::Epidemiologic Methods::Data Collection::Nutrition Assessment [Medical Subject Headings], Analytical, Diagnostic and Therapeutic Techniques and Equipment::Investigative Techniques::Epidemiologic Methods::Epidemiologic Study Characteristics as Topic::Epidemiologic Studies::Cohort Studies::Longitudinal Studies [Medical Subject Headings], Covariate, MD Multidisciplinary, Humans, cancer, Statistical Methods, Statistical Hypothesis Testing, Mathematical and Statistical Methods - Biometris, Aged, VLAG, disease, Observational error, Models, Statistical, business.industry, lcsh:R, Evaluación Nutricional, Feeding Behavior, Estudios Longitudinales, Estudios Epidemiológicos, Survival Analysis, Nutrition Assessment, lcsh:Q, Food Habits, business, Mathematics, Analytical, Diagnostic and Therapeutic Techniques and Equipment::Investigative Techniques::Epidemiologic Methods::Epidemiologic Study Characteristics as Topic::Epidemiologic Studies [Medical Subject Headings], Generalized Linear Model
Abstract: Journal Article; In epidemiologic studies, measurement error in dietary variables often attenuates association between dietary intake and disease occurrence. To adjust for the attenuation caused by error in dietary intake, regression calibration is commonly used. To apply regression calibration, unbiased reference measurements are required. Short-term reference measurements for foods that are not consumed daily contain excess zeroes that pose challenges in the calibration model. We adapted two-part regression calibration model, initially developed for multiple replicates of reference measurements per individual to a single-replicate setting. We showed how to handle excess zero reference measurements by two-step modeling approach, how to explore heteroscedasticity in the consumed amount with variance-mean graph, how to explore nonlinearity with the generalized additive modeling (GAM) and the empirical logit approaches, and how to select covariates in the calibration model. The performance of two-part calibration model was compared with the one-part counterpart. We used vegetable intake and mortality data from European Prospective Investigation on Cancer and Nutrition (EPIC) study. In the EPIC, reference measurements were taken with 24-hour recalls. For each of the three vegetable subgroups assessed separately, correcting for error with an appropriately specified two-part calibration model resulted in about three fold increase in the strength of association with all-cause mortality, as measured by the log hazard ratio. Further found is that the standard way of including covariates in the calibration model can lead to over fitting the two-part calibration model. Moreover, the extent of adjusting for error is influenced by the number and forms of covariates in the calibration model. For episodically consumed foods, we advise researchers to pay special attention to response distribution, nonlinearity, and covariate inclusion in specifying the calibration model. Yes
Published: 2014

48. Disconnected Components Detection and Rooted Shortest-Path Tree Maintenance in Networks

Author: Christian Glacet, Nicolas Hanusse, Colette Johnen, David Ilcinkas, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), ANR-16-CE40-0023,DESCARTES,Abstraction modulaire pour le calcul distribué(2016), ANR-16-CE25-0009,ESTATE,Auto-stabilisation et amélioration de la sûreté dans les environnements distribués évoluant dans le temps(2016), ANR-10-IDEX-0003,IDEX BORDEAUX,Initiative d'excellence de l'Université de Bordeaux(2010), See paper for details., and ANR-11-BS02-0014,DISPLEXITY,Calculabilité et complexité en distribué(2011)
Subjects: Routing protocol, Leader election, Theoretical computer science, Computer Networks and Communications, Computer science, 02 engineering and technology, Theoretical Computer Science, Artificial Intelligence, shortest-path, disconnected network, Node (computer science), 0202 electrical engineering, electronic engineering, information engineering, Mathematics, Discrete mathematics, Connected component, routing algorithm, business.industry, Shortest-path tree, 020206 networking & telecommunications, Task (computing), Tree (data structure), self-stabilization, Hardware and Architecture, Asynchronous communication, Shortest path problem, 020201 artificial intelligence & image processing, Enhanced Data Rates for GSM Evolution, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Daemon, business, Software, Computer network
Abstract: Many articles deal with the problem of maintaining a rooted shortest-path tree. However, after some edge deletions, some nodes can be disconnected from the connected component V r of some distinguished node r . In this case, an additional objective is to ensure the detection of the disconnection by the nodes that no longer belong to V r . We present a detailed analysis of a silent self-stabilizing algorithm. We prove that it solves this more demanding task in anonymous weighted networks with the following additional strong properties: it runs without any knowledge on the network and under the unfair daemon, that is without any assumption on the asynchronous model. Moreover, it terminates in less than 2 n + D rounds for a network of n nodes and hop-diameter D .
Published: 2014

49. Exploration of Constantly Connected Dynamic Graphs Based on Cactuses

Author: Ahmed Mouhamadou Wade, David Ilcinkas, Ralf Klasing, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), See papers for details., and ANR-11-BS02-0014,DISPLEXITY,Calculabilité et complexité en distribué(2011)
Subjects: Mobile agent, Block graph, Discrete mathematics, Symmetric graph, Cactus graph, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, law.invention, Combinatorics, Connectivity over time, 010201 computation theory & mathematics, law, Random regular graph, Clique-width, Line graph, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Exploration, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Pancyclic graph, Dynamic graphs, MathematicsofComputing_DISCRETEMATHEMATICS, Mathematics, Distance-hereditary graph
Abstract: International audience; We study the problem of exploration by a mobile entity (agent) of a class of dynamic networks, namely constantly connected dynamic graphs. This problem has already been studied in the case where the agent knows the dynamics of the graph and the underlying graph is a ring of $n$ vertices \cite{IW13}. In this paper, we consider the same problem and we suppose that the underlying graph is a cactus graph (a connected graph in which any two simple cycles have at most one vertex in common). We propose an algorithm that allows the agent to explore these dynamic graphs in at most $2^{O(\sqrt{\log n})} n$ time units. We show that the lower bound of the algorithm is $2^{\Omega(\sqrt{\log n})} n$ time units.
Published: 2014

50. On the Communication Complexity of Distributed Name-Independent Routing Schemes

Author: Nicolas Hanusse, Christian Glacet, David Ilcinkas, Cyril Gavoille, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Institut Universitaire de France (IUF), Ministère de l'Education nationale, de l’Enseignement supérieur et de la Recherche (M.E.N.E.S.R.), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), See paper for details., ANR-11-BS02-0014,DISPLEXITY,Calculabilité et complexité en distribué(2011), European Project: 258307,EC:FP7:ICT,FP7-ICT-2009-5,EULER(2010), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest, Ilcinkas, David, BLANC - Calculabilité et complexité en distribué - - DISPLEXITY2011 - ANR-11-BS02-0014 - BLANC - VALID, and Experimental UpdateLess Evolutive Routing - EULER - - EC:FP7:ICT2010-10-01 - 2014-06-30 - 258307 - VALID
Subjects: TheoryofComputation_MISCELLANEOUS, distributed routing algorithm, compact routing, Routing table, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 020206 networking & telecommunications, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, bounded stretch, 01 natural sciences, Combinatorics, Asynchronous algorithms, 010201 computation theory & mathematics, TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY, Shortest path problem, 0202 electrical engineering, electronic engineering, information engineering, [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Graph (abstract data type), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Communication complexity, name-independent, Mathematics, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: International audience; We present a distributed asynchronous algorithm that, for every undirected weighted $n$-node graph $G$, constructs name-independent routing tables for $G$. The size of each table is $\tO(\sqrt{n}\,)$, whereas the length of any route is stretched by a factor of at most~$7$ w.r.t. the shortest path. At any step, the memory space of each node is $\tO(\sqrt{n}\,)$. The algorithm terminates in time $O(D)$, where $D$ is the hop-diameter of $G$. In synchronous scenarios and with uniform weights, it consumes $\tO(m\sqrt{n} + n^{3/2}\min\set{D,\sqrt{n}\,})$ messages, where $m$ is the number of edges of $G$. In the realistic case of sparse networks of poly-logarithmic diameter, the communication complexity of our scheme, that is $\tO(n^{3/2})$, improves by a factor of $\sqrt{n}$ the communication complexity of \emph{any} shortest-path routing scheme on the same family of networks. This factor is provable thanks to a new lower bound of independent interest.
Published: 2013

Searchworks

Select search scope, currently: Articles Catalog books, media & more in Jio Institute collections Articles journal articles & other e-resources

Search

Search Constraints

Refine your results

Search Limiters

Topic

Publication Year Range

Language

Publication Type

Journal

Database

Publisher

70 results

Search Results

Select search scope, currently: Articles

Catalog

books, media & more in Jio Institute collections

Articles

journal articles & other e-resources