Topic: [info.info-ds] computer science [cs]/data structures and algorithms [cs.ds] - Searchworks@Jio Institute Digital Library Search Results

Showing total 726 results

Start Over Topic [info.info-ds] computer science [cs]/data structures and algorithms [cs.ds]

726 results

1. Generic Programming by Program Composition (position paper)

Author: Correnson, Loic, Duris, Étienne, Parigot, Didier, Roussel, Gilles, Syntactic Tools for Program Construction and Analysis (OSCAR), Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Laboratoire d'Informatique Gaspard-Monge (LIGM), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), and Duris, Etienne
Subjects: [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], ComputingMilieux_MISCELLANEOUS
Abstract: International audience
Published: 1998

2. Axel Thue's papers on repetitions in words: a translation

Author: Berstel, Jean, Berstel, Jean, Laboratoire d'Informatique Gaspard-Monge (LIGM), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), and Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS)
Subjects: [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS]
Abstract: incollection
Published: 1992

3. Accurate keyphrase extraction from scientific papers by mining linguistic information

Author: Haddoud, M., Mokhtari, A., Thierry Lecroq, Abdeddaïm, S., Lecroq, Thierry, Iana Atanassova and Marc Bertin and Philipp Mayr, Equipe Traitement de l'information en Biologie Santé (TIBS - LITIS), Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes (LITIS), Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Université de Rouen Normandie (UNIROUEN), Normandie Université (NU)-Université Le Havre Normandie (ULH), Normandie Université (NU)-Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Normandie Université (NU), and Département informatique
Subjects: [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], ComputingMilieux_MISCELLANEOUS
Abstract: International audience

4. Versatile and Generic Monitoring Solution Based on LPWAN Sensors Deployed on the Fly

Author: Maudet, Gwen, Batton-Hubert, Mireille, Maillé, Patrick, Toutain, Laurent, MAUDET, Gwen, Département Systèmes Réseaux, Cybersécurité et Droit du numérique (IMT Atlantique - SRCD), IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), École des Mines de Saint-Étienne (Mines Saint-Étienne MSE), Institut Mines-Télécom [Paris] (IMT), mEasuRing and ManagIng Network operation and Economic (ERMINE), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-RÉSEAUX, TÉLÉCOMMUNICATION ET SERVICES (IRISA-D2), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Objets communicants pour l'Internet du futur (OCIF), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-RÉSEAUX, TÉLÉCOMMUNICATION ET SERVICES (IRISA-D2), and Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)
Subjects: [INFO.INFO-AI] Computer Science [cs]/Artificial Intelligence [cs.AI], [INFO.INFO-NI] Computer Science [cs]/Networking and Internet Architecture [cs.NI], [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], [INFO.INFO-AO]Computer Science [cs]/Computer Arithmetic, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation, [STAT.ML] Statistics [stat]/Machine Learning [stat.ML], [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], [STAT.ML]Statistics [stat]/Machine Learning [stat.ML], [INFO.INFO-ET] Computer Science [cs]/Emerging Technologies [cs.ET], [INFO.INFO-ET]Computer Science [cs]/Emerging Technologies [cs.ET], [INFO.INFO-AO] Computer Science [cs]/Computer Arithmetic, [INFO.INFO-MO] Computer Science [cs]/Modeling and Simulation
Abstract: Setting up IoT monitoring solutions requires a significant workforce for deployment and maintenance. This becomes particularly costly when a massive number of sensors are deployed. In this paper, we propose a generic solution based on energyautonomous LPWAN sensors deployed on the fly. On one side, we propose an efficient management strategy that adapts the transmission period of sensors in order to receive a chosen amount of information on each sensor cluster that emits similar information. Moreover, we develop a method that generates realtime estimates based on the sensor message history. After showing the relevance of our estimation method, we show that our sensor management method is efficient by comparing it to a baseline. Additionally, our tools are robust to the hazards occurring in the IoT: sensor arrivals and departures, noisy measuring in a highly variable environment, misplacement of sensors. Overall, this paper proposes a way to scale up IoT, breaking the deployment cost barrier and paving the way for universal and versatile monitoring solutions.
Published: 2023

5. Dimensionnement des centres de données autonomes pour lutter contre le surdimensionnement des parties informatiques et électriques

Author: BENAISSA, Manal, da Costa, Georges, Nicod, Jean-Marc, BENAISSA, Manal, DATAcenter avec Zero Emission de CO2 : un pas plus loin - - DATAZERO22019 - ANR-19-CE25-0016 - AAPG2019 - VALID, Ingénierie et Innovation par les sciences physiques, les savoir-faire technologiques et l'interdisciplinarité - - EIPHI2017 - ANR-17-EURE-0002 - EURE - VALID, and Femto-st, AS2M
Subjects: Green Datacenter, Renewable energy, [SPI.AUTO] Engineering Sciences [physics]/Automatic, Scheduling, [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Quality of Service, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Sizing reduction
Abstract: During the two last decades, sustainability of IT infrastructures like datacenters became a major concern for computer giants like Google or Amazon. Datacenters powered with renewable energy have been proposed. But because of the intermittency of these power alternatives, these platforms remains connected to the classical power grid. IT structure and electrical constraints were often questioned separately, leading to a non-efficient global system. In this paper, an energy self-sufficient green datacenter is modeled and designed, by proposing an electrically autonomous infrastructure including wind turbines, solar panels and its own short and longterm storage devices mainly based on batteries and hydrogen system. Existing sizing approaches limit themselves to a perfect QoS leading to an overestimation of the needed equipment. In this paper we show how to reduce and combat this overprovioning by questioning its impact on the QoS and needed equipment: decreasing the number of computing or storage elements (servers and batteries). As an example, decreasing the targeted QoS from 100 to 95% more than halves the needed number of servers, while a decrease of 30% of the battery capacity has a negligible impact on the electrical infrastructure., Au cours des deux dernières décennies, la durabilité des infrastructures informatiques telles que les centres de données est devenue une préoccupation majeure pour les géants de l'informatique comme Google ou Amazon. Des centres de données alimentés par des énergies renouvelables ont été proposés. Mais en raison de l'intermittence de ces alternatives énergétiques, ces plateformes restent connectées au réseau électrique classique. La structure informatique et les contraintes électriques ont souvent été questionnées séparément, conduisant à un système global non efficace. Dans cet article, un centre de données vert autosuffisant en énergie est modélisé et conçu, en proposant une infrastructure électriquement autonome comprenant des éoliennes, des panneaux solaires et ses propres dispositifs de stockage à court et long terme principalement basés sur des batteries et un système à hydrogène. Les approches de dimensionnement existantes se limitent à une qualité de service parfaite, ce qui conduit à une surestimation des équipements nécessaires. Dans cet article, nous montrons comment réduire et combattre cette surestimation en questionnant son impact sur la qualité de service et les équipements nécessaires : en diminuant le nombre d'éléments de calcul ou de stockage (serveurs et batteries). A titre d'exemple, la diminution de la qualité de service visée de 100 à 95% réduit de plus de la moitié le nombre de serveurs nécessaires, tandis qu'une diminution de 30% de la capacité des batteries a un impact négligeable sur l'infrastructure électrique.
Published: 2022

6. Calibration of a multi-mobile coil magnetic manipulation system utilizing a control-oriented magnetic model

Author: Nahashon O. Osinde, Maxime Etiévant, Jean Bosco Byiringiro, Nicolas Andreff, and Femto-st, AS2M
Subjects: [SPI.AUTO] Engineering Sciences [physics]/Automatic, Control and Systems Engineering, Mechanical Engineering, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Electrical and Electronic Engineering, Computer Science Applications
Abstract: In this paper, we address the calibration of a family of magnetic manipulation systems composed of several coils that are moved around by serial robot manipulators. We show in this paper that the calibration of the whole system ultimately results in calibrating the manipulator and coil separately up to an unknown rigid transformation. For calibration of the coil, we propose to use a model that has not been used so far in the literature; a control-oriented model which is su ciently accurate and computes the magnetic field in real time. A protocol for calibrating the magnetic manipulation system using the Nelder-Mead algorithm to estimate the model parameters is presented. Calibration was performed through simulations and validated experimentally on a physical system. It was observed that the root mean square error was reduced by 37% after calibration of the physical system, indicating an improvement in accurately estimating the magnetic model.
Published: 2022

7. Asynchronous Gathering in a Torus

Author: Kamei, Sayaka, Lamani, Anissa, Ooshita, Fukuhito, Tixeuil, Sébastien, Wada, Koichi, Tixeuil, Sébastien, Auto-stabilisation et amélioration de la sûreté dans les environnements distribués évoluant dans le temps - - ESTATE2016 - ANR-16-CE25-0009 - AAPG2016 - VALID, Sûreté et preuve de protocoles adaptatifs pour robots oublieux - - SAPPORO2019 - ANR-19-CE25-0005 - AAPG2019 - VALID, Graduate School of Advanced Science and Engineering [Higashi-Hiroshima], Hiroshima University, Laboratoire des sciences de l'ingénieur, de l'informatique et de l'imagerie (ICube), École Nationale du Génie de l'Eau et de l'Environnement de Strasbourg (ENGEES)-Université de Strasbourg (UNISTRA)-Institut National des Sciences Appliquées - Strasbourg (INSA Strasbourg), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Les Hôpitaux Universitaires de Strasbourg (HUS)-Centre National de la Recherche Scientifique (CNRS)-Matériaux et Nanosciences Grand-Est (MNGE), Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Institut de Chimie du CNRS (INC)-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Institut de Chimie du CNRS (INC)-Centre National de la Recherche Scientifique (CNRS)-Réseau nanophotonique et optique, Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Centre National de la Recherche Scientifique (CNRS), Nara Institute of Science and Technology - Graduate School of Information Science (NAIST), Nara Institute of Science and Technology, Networks and Performance Analysis (NPA), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Faculty of Science and Engineering, Hosei University, Hosei University, 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-19-CE25-0005,SAPPORO,Sûreté et preuve de protocoles adaptatifs pour robots oublieux(2019), Institut National des Sciences Appliquées - Strasbourg (INSA Strasbourg), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Strasbourg (UNISTRA)-Centre National de la Recherche Scientifique (CNRS)-École Nationale du Génie de l'Eau et de l'Environnement de Strasbourg (ENGEES)-Réseau nanophotonique et optique, Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Matériaux et nanosciences d'Alsace (FMNGE), Institut de Chimie du CNRS (INC)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS)-Institut de Chimie du CNRS (INC)-Université de Strasbourg (UNISTRA)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS), Laboratory of Information, Network and Communication Sciences (LINCS), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut Mines-Télécom [Paris] (IMT)-Sorbonne Université (SU), and Hosei University [Chiyoda]
Subjects: FOS: Computer and information sciences, [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Theory of computation �� Distributed algorithms, Robots gathering, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-RB] Computer Science [cs]/Robotics [cs.RO], Autonomous distributed systems, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], Torus, Computer Science::Robotics, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], Computer Science - Distributed, Parallel, and Cluster Computing, [INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG], [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Distributed algorithms, [INFO.INFO-RB]Computer Science [cs]/Robotics [cs.RO], [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC], Distributed, Parallel, and Cluster Computing (cs.DC), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Abstract: We consider the gathering problem for asynchronous and oblivious robots that cannot communicate explicitly with each other, but are endowed with visibility sensors that allow them to see the positions of the other robots. Most of the investigations on the gathering problem on the discrete universe are done on ring shaped networks due to the number of symmetric configuration. We extend in this paper the study of the gathering problem on torus shaped networks assuming robots endowed with local weak multiplicity detection. That is, robots cannot make the difference between nodes occupied by only one robot from those occupied by more than one robots unless it is their current node. As a consequence, solutions based on creating a single multiplicity node as a landmark for the gathering cannot be used. We present in this paper a deterministic algorithm that solves the gathering problem starting from any rigid configuration on an asymmetric unoriented torus shaped network., Comment: 41 pages
Published: 2022
Full Text: View/download PDF

8. Planning in-hand dexterous micro-manipulation using 3-D rotations decomposition

Author: Pardeep Kumar, Redwan Dahmouche, Michaël Gauthier, Femto-st, AS2M, Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174) (FEMTO-ST), Université de Technologie de Belfort-Montbeliard (UTBM)-Ecole Nationale Supérieure de Mécanique et des Microtechniques (ENSMM)-Université de Franche-Comté (UFC), and Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Computer science, business.industry, Computation, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 030204 cardiovascular system & hematology, Object (computer science), [SPI.AUTO]Engineering Sciences [physics]/Automatic, 03 medical and health sciences, 0302 clinical medicine, Planar, [SPI.AUTO] Engineering Sciences [physics]/Automatic, Dexterous manipulation, Robustness (computer science), 030220 oncology & carcinogenesis, Decomposition (computer science), Computer vision, Artificial intelligence, Computer-aided software engineering, Planning algorithms, business, ComputingMilieux_MISCELLANEOUS
Abstract: This paper aims to contribute to the improvement of dexterity in contact micro-manipulation by performing in-hand dexterous micro-manipulation planning. Previous experimental works on planar micro-manipulation showed that such an approach allows for large rotations of arbitrary shaped objects. Moving from planar to 3-D manipulation significantly increases the complexity of the manipulation planning, especially when considering the rolling of the fingers on the object during the manipulation. We propose in this paper a dexterous manipulation planning algorithm that leverages the complexity of 3-D manipulation planning by decomposing the desired 3-D rotations into three successive rotations within two different planes. Optimal paths of the manipulating fingers are thus obtained in the planar spaces and then combined to form the trajectories in the 3-D space. Besides the relevance of the approach, the simulation results show that exploiting adhesion forces improves the robustness of the manipulation and extends the manipulation capabilities, but at the expense of the computation time.
Published: 2021

9. Graph-based Pattern Detection in Spatio-Temporal Phenomena

Author: Oberoi, Kamaldeep Singh, Del Mondo, Géraldine, Oberoi, Kamaldeep Singh, Université de Rouen Normandie (UNIROUEN), Normandie Université (NU), Equipe Systèmes de Transport Intelligent (STI - LITIS), Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes (LITIS), Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Université de Rouen Normandie (UNIROUEN), Normandie Université (NU)-Université Le Havre Normandie (ULH), Normandie Université (NU)-Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU), and Equipe Apprentissage (DocApp - LITIS)
Subjects: [INFO.INFO-AI] Computer Science [cs]/Artificial Intelligence [cs.AI], [INFO.INFO-IR]Computer Science [cs]/Information Retrieval [cs.IR], [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO]Computer Science [cs], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-MO] Computer Science [cs]/Modeling and Simulation, [INFO.INFO-IR] Computer Science [cs]/Information Retrieval [cs.IR], [INFO] Computer Science [cs], [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Abstract: Spatio-temporal (ST) models are often used for analyzing ST phenomena. One such analysis technique is to detect patterns in the phenomenon to understand its evolution and model the behaviour of its entities over space-time. In this paper, we focus on using a dynamic graph-based representation for modeling ST phenomena, within which structural patterns, also modeled using dynamic graphs, can be detected. We illustrate the concept of pattern using two applications - road traffic and invasive team sports. For both these applications, we present the graph model as well as the corresponding patterns. Then we formalize the problem of pattern detection as that of subgraph isomorphism for dynamic graphs. Finally, we present the results of our algorithm to solve this problem. The initial results described in this paper, obtained using random graphs, present a baseline for the future tests of the algorithm., Les modèles spatio-temporels (ST) sont souvent utilisés pour analyser les phénomènes ST. Une de ces techniques d'analyse consiste à détecter des motifs dans le phénomène pour comprendre son évolution et modéliser le comportement de ses entités dans l'espace et le temps. Dans cet article, nous nous concentrons sur l'utilisation d'une représentation fondée sur les graphes dynamiques pour la modélisation des phénomènes ST, au sein duquel des motifs structurels, également modélisés sous forme de graphes dynamiques, peuvent être détectés. Nous illustrons le concept de motif par deux exemples applicatifs - le trafic routier et les sports collectifs. Pour chacun d'eux, nous présentons une modélisation du graphe ainsi que des motifs associés. Ensuite, nous formalisons le problème de la détection de motifs comme celui de l'isomorphisme de sous-graphe pour les graphes dynamiques. Enfin, nous présentons les résultats de notre algorithme pour résoudre ce problème. Les premiers résultats décrits dans cet article, qui sont obtenus en utilisant les graphes aléatoires, présentent une base de référence pour les futurs tests de l'algorithme.
Published: 2021

10. Efficient Weighted Average Calculation Algorithm

Author: Tambiah, Matthew and Tambiah, Matthew
Subjects: [MATH.MATH-GM] Mathematics [math]/General Mathematics [math.GM], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS]
Abstract: This paper presents an efficient algorithm (method) for calculating Weighted Averages called the "Fast Weighted Average calculation method. In general, the algorithm presented in textbooks for calculating a Weighted Average of n elements (each with a Values and a Weight) will require n multiplication operations. This paper presents a calculation algorithm for calculating the Weighted Average of elements using at most (n − 1) multiplication operations when using Normalized Weights.
Published: 2021

11. On a problem of team hiring

Author: Liu, Jin-Yi, Liu, Jin-Yi, School of Computer & Communication Engineering (CCE), and Liaoning Shihua University (LNPU)
Subjects: [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], ACM: G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS/G.2.1: Combinatorics, ACM: G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO]Computer Science [cs], [MATH] Mathematics [math], [INFO] Computer Science [cs], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [MATH]Mathematics [math], ACM: G.: Mathematics of Computing
Abstract: Given two positive integers n and k with k ≤ n, let X denote the family of all the k-subsets of [n] := {1, 2, ..., n}. In this paper, assuming that the k-subsets in X hold some order of ranks, we consider the expected number of left-to-right maxima in some sequential ordering of X , under a random permutation of [n]. In the case k = 1, it is well-known that the answer is the nth harmonic number Hn = 1 + 1/2 + ... + 1/n = ln(n) + O(1). For general k, the contribution of this paper is about E * lex (n, k) and E * col (n, k), the expected numbers of left-to-right maxima respectively in the lexicographical and colexicographical orderings of X , achieved when the k-subsets in X hold their respective worst orders of ranks (to make the two values as large as possible). We show that E * lex (n, k) = E * col (n, k), and give an exact formula (not in closed form) for them. For estimating them, we further show that when k' := min{k, n − k} is fixed and n is big enough, they are asymtotic to (ln(n))^k'/k'!. The problem we consider here can be viewed as an extension to the assistant-hiring problem, presented in the textbook Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein, for introducing probabilistic analysis and randomized algorithms.
Published: 2021

12. Set-Membership Computation of Integrals with Uncertain Endpoints

Author: Julien Alexandre Dit Sandretto, Olivier Mullier, Laboratoire Modélisation et Analyse de Systèmes en Interaction (LMeASI), 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), Unité d'Informatique et d'Ingénierie des Systèmes (U2IS), École Nationale Supérieure de Techniques Avancées (ENSTA Paris), Mullier, Olivier, and Laboratoire d'Intégration des Systèmes et des Technologies (LIST (CEA))
Subjects: 0209 industrial biotechnology, Computer science, Computation, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 010103 numerical & computational mathematics, 02 engineering and technology, Interval (mathematics), 01 natural sciences, Set (abstract data type), Interval Methods, 020901 industrial engineering & automation, Integral, [INFO.INFO-SY]Computer Science [cs]/Systems and Control [cs.SY], Applied mathematics, 0101 mathematics, Set-membership Computation, ComputingMilieux_MISCELLANEOUS, Continuous function, business.industry, Robotics, Function (mathematics), [INFO.INFO-NA]Computer Science [cs]/Numerical Analysis [cs.NA], Nonlinear system, Artificial intelligence, business, Global optimization problem
Abstract: An efficient guaranteed method for the computation of the integral of a nonlinear continuous function between two interval endpoints is proposed. This computation can be of interest for the computation of global optimization problems where such integrals occur like in robotics. The method results in the computation of the minimum and maximum of these integrals and provides the endpoints at stake. The complexity of the resulting algorithms is discussed, it depends on the number of roots of the function to be integrated. The computation is illustrated on several examples.
Published: 2020

13. A distributed, probabilistic, hysteretic, retroactive algorithm to locally weaken the CAP/Brewer’s theorem when reading data on a distributed computer system

Author: FAUVELLE, Jean-Philippe, FAUVELLE, Jean-Philippe, Airbus Defence & Space [Elancourt] (Airbus group), and EDILE SAS
Subjects: [INFO.INFO-DB]Computer Science [cs]/Databases [cs.DB], Concurrent computing, Partition tolerance, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-SE] Computer Science [cs]/Software Engineering [cs.SE], CAP theorem, Availability, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-SE]Computer Science [cs]/Software Engineering [cs.SE], Computer science, Distributed computing, [INFO.INFO-PF]Computer Science [cs]/Performance [cs.PF], [INFO.INFO-IT]Computer Science [cs]/Information Theory [cs.IT], [INFO.INFO-PF] Computer Science [cs]/Performance [cs.PF], [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], [INFO.INFO-DB] Computer Science [cs]/Databases [cs.DB], Consistency, [INFO.INFO-IT] Computer Science [cs]/Information Theory [cs.IT], [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Brewer's theorem
Abstract: Full understanding of this paper requires expertise in computer science, software engineering and algorithmics.; The CAP (Consistency, Availability, Partition tolerance) also known as Brewer's theorem, states that it is impossible, on a distributed computer system, to guarantee at the same time the three qualities mentioned above. This issue affects all existing distributed engines and systems, which forces the administrators of these engines and systems to favor two qualities to the detriment of a third, when possible, despite the consequences. This paper technically and formally describes an inventive algorithm to locally weaken the said theorem when reading the data. This process combines three elements: a real-time system of key-value pairs distributed in memory cloud; a multi-planar index with concurrency avoidance; a distributed consolidated reading method called "LC4" based on a hysterical retroactive probabilistic effect. This inventive algorithm was implemented and tested successfully, jointly with a second invention playing the role of an application delivery controller (“A heuristic algorithm imitating social behaviours for intelligent routing of application flows” ⟨hal-02471814⟩ https://hal.archives-ouvertes.fr/hal-02471814). Full understanding of this paper requires expertise in computer science, software engineering and algorithmics.
Published: 2020

14. Approximate Counting via the Poisson-Laplace-Mellin Method

Author: Michael Fuchs, Chung-Kuei Lee, and Helmut Prodinger
Subjects: approximate counting, digital search tree, js-admissibility, laplace transform, mellin transform, [info.info-ds] computer science [cs]/data structures and algorithms [cs.ds], [info.info-dm] computer science [cs]/discrete mathematics [cs.dm], [math.math-co] mathematics [math]/combinatorics [math.co], [info.info-cg] computer science [cs]/computational geometry [cs.cg], Mathematics, QA1-939
Abstract: Approximate counting is an algorithm that provides a count of a huge number of objects within an error tolerance. The first detailed analysis of this algorithm was given by Flajolet. In this paper, we propose a new analysis via the Poisson-Laplace-Mellin approach, a method devised for analyzing shape parameters of digital search trees in a recent paper of Hwang et al. Our approach yields a different and more compact expression for the periodic function from the asymptotic expansion of the variance. We show directly that our expression coincides with the one obtained by Flajolet. Moreover, we apply our method to variations of approximate counting, too.
Published: 2012
Full Text: View/download PDF

15. On Greedy Trie Execution

Author: Zbigniew Gołębiewski and Filip Zagórski
Subjects: trie, leader election, [info.info-ds] computer science [cs]/data structures and algorithms [cs.ds], [info.info-dm] computer science [cs]/discrete mathematics [cs.dm], [math.math-co] mathematics [math]/combinatorics [math.co], [info.info-cg] computer science [cs]/computational geometry [cs.cg], Mathematics, QA1-939
Abstract: In the paper "How to select a looser'' Prodinger was analyzing an algorithm where $n$ participants are selecting a leader by flipping fair coins, where recursively, the 0-party (those who i.e. have tossed heads) continues until the leader is chosen. We give an answer to the question stated in the Prodinger's paper – what happens if not a 0-party is recursively looking for a leader but always a party with a smaller cardinality. We show the lower bound on the number of rounds of the greedy algorithm (for fair coin).
Published: 2012
Full Text: View/download PDF

16. Kinematics, Design and Experimental Validation of a Novel Parallel Robot for Two-Fingered Dexterous Manipulation

Author: Sébastien Thibaud, Redwan Dahmouche, Wissem Haouas, Guillaume J. Laurent, Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174) (FEMTO-ST), Université de Technologie de Belfort-Montbeliard (UTBM)-Ecole Nationale Supérieure de Mécanique et des Microtechniques (ENSMM)-Université de Franche-Comté (UFC), Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC)-Centre National de la Recherche Scientifique (CNRS), and femto-st, dma
Subjects: 0209 industrial biotechnology, Computer science, GRASP, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Parallel manipulator, Control engineering, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 02 engineering and technology, Kinematics, [PHYS.MECA]Physics [physics]/Mechanics [physics], Degrees of freedom (mechanics), 021001 nanoscience & nanotechnology, [SPI.AUTO]Engineering Sciences [physics]/Automatic, Mechanism (engineering), Computer Science::Robotics, 020901 industrial engineering & automation, [SPI.AUTO] Engineering Sciences [physics]/Automatic, Robot, [PHYS.MECA] Physics [physics]/Mechanics [physics], 0210 nano-technology, Actuator
Abstract: International audience; Two-fingered manipulation robotic systems are widely used in many applications and notably at small scales. The commonly employed solution is based on the attachment of a gripper on a robot. This paper introduces a new eight degrees of freedom (DoF) mechanism intended for two-fingered dexterous manipulation. The eight DoFs are obtained via a parallel architecture moved by eight actuators that are attached to the base of the robot. The novelty lies in the use of a 2-DoF configurable platform that insures two relative rotations of the gripper jaws (opening and twisting) in addition to the 6-DoF Cartesian movements. The paper presents the kinematics and the design of a proof-of-concept able to grasp, roll, translate and rotate objects in a single compact design. A prototype is operated to manipulate and insert a 2-mm screw.
Published: 2019

17. Optimal Prefix and Suffix Queries on Texts

Author: Maxime Crochemore, Costas S. Iliopoulos, and M. Sohel Rahman
Subjects: algorithms, pattern matching, index, data structures, suffix trees, [info.info-ds] computer science [cs]/data structures and algorithms [cs.ds], [info.info-dm] computer science [cs]/discrete mathematics [cs.dm], [math.math-co] mathematics [math]/combinatorics [math.co], [info.info-cg] computer science [cs]/computational geometry [cs.cg], Mathematics, QA1-939
Abstract: In this paper, we study a restricted version of the position restricted pattern matching problem introduced and studied by Mäkinen and Navarro [Position-Restricted Substring Searching, LATIN 2006]. In the problem handled in this paper, we are interested in those occurrences of the pattern that lies in a suffix or in a prefix of the given text. We achieve optimal query time for our problem against a data structure which is an extension of the classic suffix tree data structure. The time and space complexity of the data structure is dominated by that of the suffix tree. Notably, the (best) algorithm by Mäkinen and Navarro, if applied to our problem, gives sub-optimal query time and the corresponding data structure also requires more time and space.
Published: 2007
Full Text: View/download PDF

18. Efficient Mining Top-k Regular-Frequent Itemset Using Compressed Tidsets

Author: Komate Amphawan, Athasit Surarerks, Philippe Lenca, Département Logique des Usages, Sciences sociales et Sciences de l'Information ( LUSSI ), Université européenne de Bretagne ( UEB ) -Télécom Bretagne-Institut Mines-Télécom [Paris], Engineering Laboratory in Theoretical Enumerable System (University of Chulalongkorn) ( ELITE ), Lab-STICC_TB_CID_DECIDE, Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance ( Lab-STICC ), École Nationale d'Ingénieurs de Brest ( ENIB ) -Université de Bretagne Sud ( UBS ) -Université de Brest ( UBO ) -Télécom Bretagne-Institut Brestois du Numérique et des Mathématiques ( IBNM ), Université de Brest ( UBO ) -Université européenne de Bretagne ( UEB ) -ENSTA Bretagne-Institut Mines-Télécom [Paris]-Centre National de la Recherche Scientifique ( CNRS ) -École Nationale d'Ingénieurs de Brest ( ENIB ) -Université de Bretagne Sud ( UBS ) -Université de Brest ( UBO ) -Télécom Bretagne-Institut Brestois du Numérique et des Mathématiques ( IBNM ), Université de Brest ( UBO ) -Université européenne de Bretagne ( UEB ) -ENSTA Bretagne-Institut Mines-Télécom [Paris]-Centre National de la Recherche Scientifique ( CNRS ), Département Logique des Usages, Sciences sociales et Sciences de l'Information (LUSSI), Université européenne de Bretagne - European University of Brittany (UEB)-Télécom Bretagne-Institut Mines-Télécom [Paris] (IMT), Engineering Laboratory in Theoretical Enumerable System (University of Chulalongkorn) (ELITE), Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance (Lab-STICC), École Nationale d'Ingénieurs de Brest (ENIB)-Université de Bretagne Sud (UBS)-Université de Brest (UBO)-Télécom Bretagne-Institut Brestois du Numérique et des Mathématiques (IBNM), Université de Brest (UBO)-Université européenne de Bretagne - European University of Brittany (UEB)-École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne)-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS)-École Nationale d'Ingénieurs de Brest (ENIB)-Université de Bretagne Sud (UBS)-Université de Brest (UBO)-Télécom Bretagne-Institut Brestois du Numérique et des Mathématiques (IBNM), Université de Brest (UBO)-Université européenne de Bretagne - European University of Brittany (UEB)-École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne)-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS), Télécom Bretagne, Bibliothèque, Institut Mines-Télécom [Paris] (IMT)-Télécom Bretagne-Université européenne de Bretagne - European University of Brittany (UEB), Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance (UMR 3192) (Lab-STICC), Université européenne de Bretagne - European University of Brittany (UEB)-Université de Bretagne Sud (UBS)-Université de Brest (UBO)-Institut Brestois du Numérique et des Mathématiques (IBNM), Université de Brest (UBO)-Télécom Bretagne-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS), and Télécom Bretagne (devenu IMT Atlantique), Ex-Bibliothèque
Subjects: [INFO.INFO-AI] Computer Science [cs]/Artificial Intelligence [cs.AI], Single pass, Association rule learning, Computer science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Regular itemsets, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 02 engineering and technology, Top-k itemsets, computer.software_genre, [ INFO.INFO-LG ] Computer Science [cs]/Machine Learning [cs.LG], [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], Set (abstract data type), [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], 020204 information systems, 0202 electrical engineering, electronic engineering, information engineering, [INFO.INFO-DB] Computer Science [cs]/Databases [cs.DB], [ INFO.INFO-AI ] Computer Science [cs]/Artificial Intelligence [cs.AI], Representation (mathematics), [ INFO.INFO-DS ] Computer Science [cs]/Data Structures and Algorithms [cs.DS], TRACE (psycholinguistics), [INFO.INFO-DB]Computer Science [cs]/Databases [cs.DB], [INFO.INFO-LG] Computer Science [cs]/Machine Learning [cs.LG], Frequent itemsets, Task (computing), Regular pattern, Key (cryptography), 020201 artificial intelligence & image processing, Data mining, computer
Abstract: International audience; Association rule discovery based on support-confidence frame-work is an important task in data mining. However, the occurrence frequency (support) of a pattern (itemset) may not be a sufficient criterion for discovering interesting patterns. Temporal regularity, which can be a trace of behavior, with frequency behavior can be revealed as an important key in several applications. A pattern can be regarded as a regular pattern if it occurs regularly in a user-given period. In this paper, we consider the problem of mining top-k regular-frequent itemsets from transactional databases without support threshold. A new concise representation, called compressed transaction-ids set (compressed tidset), and a single pass algorithm, called TR-CT (Top-k Regular frequent itemset mining based on Compressed Tidsets), are proposed to maintain occurrence information of patterns and discover k regular itemsets with highest supports, respectively. Experimental results show that the use of the compressed tidset representation achieves highly efficiency in terms of execution time and memory consumption, especially on dense datasets.
Published: 2012

19. An invariance principle for random planar maps

Author: Grégory Miermont
Subjects: random planar map, invariance principle, multitype spatial galton-watson tree, brownian snake, [info.info-ds] computer science [cs]/data structures and algorithms [cs.ds], [info.info-dm] computer science [cs]/discrete mathematics [cs.dm], [math.math-co] mathematics [math]/combinatorics [math.co], Mathematics, QA1-939
Abstract: We show a new invariance principle for the radius and other functionals of a class of conditioned `Boltzmann-Gibbs'-distributed random planar maps. It improves over the more restrictive case of bipartite maps that was discussed in Marckert and Miermont (2006). As in the latter paper, we make use of a bijection between planar maps and a class of labelled multitype trees, due to Bouttier et al. (2004). We also rely on an invariance principle for multitype spatial Galton-Watson trees, which is proved in a companion paper.
Published: 2006
Full Text: View/download PDF

20. A Financial Multi-Attribute Decision Problem

Author: Andreica, Madalina Ecaterina, Dobre, Ion, Andreica, Mugurel Ionut, Andreica, Mugurel Ionut, The Faculty of Economic Cybernetics, Statistics and Informatics, Academia de Studii Economice din Bucureşti (CSIE ASE), The Bucharest Academy of Economic Studies / Academia de Studii Economice din Bucureşti (A.S.E.), Parallel and Distributed Systems Laboratory [Bucarest], University Politehnica of Bucarest, and The paper represents also a portion of the results provided by the research for the Grant 1805 under the CNCS-UEFISCDI IDEI Program PN II 2009-2011 with the title: 'Exploratory research concerning the development of an intelligent system meant to optimize financial decisions' www.intelsys.ase.ro Research leader: Prof. Adrian Victor Badescu PhD.
Subjects: ELECTRE, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], ACM G, JEL: C - Mathematical and Quantitative Methods/C.C5 - Econometric Modeling, Onicescu, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], JEL: C - Mathematical and Quantitative Methods/C.C3 - Multiple or Simultaneous Equation Models • Multiple Variables, [SHS.ECO]Humanities and Social Sciences/Economics and Finance, multi-attribute decision making, multi-attribute decision making,TOPSIS,ELECTRE,Onicescu, JEL: C - Mathematical and Quantitative Methods/C.C4 - Econometric and Statistical Methods: Special Topics, JEL: C - Mathematical and Quantitative Methods/C.C6 - Mathematical Methods • Programming Models • Mathematical and Simulation Modeling, TOPSIS, [SHS.ECO] Humanities and Social Sciences/Economics and Finance
Abstract: Efficient implementations of the algorithms used in this paper were based on the 3rd authors' experience in participating in algorithmic competitions (see the related_materials zip archive).; International audience; The purpose of this paper consists in modelling as a multi-attribute decision making problem the process of selecting the best financing alternative for the acquisition of a car out of the following financial alternatives: bank loan, financial leasing, rates or even paying cash, although mostly unlikely. The problem was then solved using the TOPSIS, ELECTRE I and ONICESCU methods and several conclusions were drawn from the analysis.
Published: 2010

21. Rétropropagation optimale de réseau profonds à forme de Joins

Author: Guillaume Pallez, Olivier Beaumont, Alena Shilova, Julien Herrmann, Pallez (Aupy), Guillaume, Ordonnancement de données pour le calcul haute-performance - - DASH2017 - ANR-17-CE25-0004 - AAPG2017 - VALID, High-End Parallel Algorithms for Challenging Numerical Simulations (HiePACS), 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)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-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), Topology-Aware System-Scale Data Management for High-Performance Computing (TADAAM), This work is supported in part by the Project Région Nouvelle Aquitaine 2018-1R50119 'HPC scalable ecosystem'., ANR-17-CE25-0004,DASH,Ordonnancement de données pour le calcul haute-performance(2017), Project Région Nouvelle Aquitaine 2018-1R50119 'HPC scalable ecosystem', Inria, and 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)-Inria Bordeaux - Sud-Ouest
Subjects: Theoretical computer science, Automatic differentiation, Computer science, General Mathematics, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], General Physics and Astronomy, Backpropagation, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 010103 numerical & computational mathematics, 02 engineering and technology, Mémoire, 01 natural sciences, Scheduling (computing), [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], Deep Learning, [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], Memory training, Memory, 0202 electrical engineering, electronic engineering, information engineering, [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], 0101 mathematics, Time complexity, Pebble game, business.industry, Deep learning, Pebble gam, General Engineering, 020206 networking & telecommunications, Articles, [INFO.INFO-LG] Computer Science [cs]/Machine Learning [cs.LG], Homogeneous, Bounded function, Neural Networks, Computer, Artificial intelligence, Rétropropagation, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], business, Algorithms
Abstract: In the context of Deep Learning training, memory needs to store activations can prevent the user to consider large models and large batch sizes. A possible solution is to rely on model parallelism to distribute the weights of the model and the activations over distributedmemory nodes. In this paper, we consider another purely sequential approach to save memory using checkpointing techniques. Checkpointing techniques have been introduced in the context of Automatic Differentiation. They consist in storing some, but not all activations during the feed-forward network training phase, and then to recompute missing values during the backward phase. Using this approach, it is possible, at the price of re-computations, to use a minimal amount of memory. The case of a single homogeneous chain i.e.the case of a network whose all stages are identical and form a chain, is well understood and optimal solutions based on dynamic programming have been proved in the Automatic Differentiation literature. The networks encountered in practice in the context of Deep Learning are much more diverse, both in terms of shape and heterogeneity. The present paper can be seen as an attempt to extend the class of graphs that can be solved optimally. Indeed, we provide an optimal algorithm, based on dynamic programming, for the case of several chains that gathers when computing the loss function. This model typically corresponds to the case of Siamese or Cross Modal Networks.; L’espace mémoire nécessaire pour l’apprentissage de réseaux profonds peut empêcher l’utilisateur de considérer de grands modèles. Dans ce travail nous discutons l’utilisation des techniques d’ordonnancement sous contraintes mémoire utilisées en différentiation automatique (AD) pour exécuter des graphes de rétropropagation sous contraintes mémoires.Le cas d’une chaine simple et homogène est maitrisé et la littérature en différentiation automatique offre de nombreuses techniques et solutions optimales sous diverses contraintes. Dans le cadre de l’apprentissage profond, les réseaux rencontrés sont souvent plus structurés et diverses(forme, hétérogénéité).Dans ce travail nous définissons la classe des graphes de rétropropagation et nous étendons l’ensemble des grahes sur lesquels on peut calculer en temps polynomial une solution optimale (en terme de temps d’exécution) sous contraintes mémoire.En particulier, nous considérons le cas des join qui correspondent à des modèles tels que les r éseaux siamois ou cross-modaux.
Published: 2019

22. Credible Autocoding of The Ellipsoid Algorithm Solving Second-Order Cone Programs

Author: Pierre-Loïc Garoche, Eric Feron, Raphael Cohen, Georgia Institute of Technology [Atlanta], ONERA / DTIS, Université de Toulouse [Toulouse], ONERA-PRES Université de Toulouse, and André, Cécile
Subjects: 0209 industrial biotechnology, Mathematical optimization, Computer science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Ellipsoid method, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 020207 software engineering, 02 engineering and technology, [INFO.INFO-IA]Computer Science [cs]/Computer Aided Engineering, Cone (formal languages), [INFO.INFO-IA] Computer Science [cs]/Computer Aided Engineering, 020901 industrial engineering & automation, [INFO.INFO-MS] Computer Science [cs]/Mathematical Software [cs.MS], Convex optimization, 0202 electrical engineering, electronic engineering, information engineering, ELLIPSOIDE, Autocoding, GENERATION AUTOMATIQUE, [INFO.INFO-MS]Computer Science [cs]/Mathematical Software [cs.MS]
Abstract: International audience; The efficiency of modern optimization meth- ods, coupled with increasing computational resources, has led to the possibility of real-time optimization algorithms acting in guidance of systems. Unfortunately, those algo- rithms are still seen as new and obscure and are not considered as a viable option for safety critical roles. This paper deals with the formal verification of convex optimization algorithms. Additionally, we demonstrate how theoretical proofs of real-time convex optimization algo- rithms can be used to describe functional properties at the code level, thereby making it accessible for the formal methods community. In seeking zero-bug software, we use the Credible Autocoding framework. We focused our attention on the Ellipsoid Algorithm solving second-order cone programs (SOCP). The paper also considers floating- point errors and gives a framework to numerically validate the method.
Published: 2018

23. When Can We Answer Queries Using Result-Bounded Data Interfaces?

Author: Antoine Amarilli, Michael Benedikt, Département Informatique et Réseaux (INFRES), Télécom ParisTech, Data, Intelligence and Graphs (DIG), Laboratoire Traitement et Communication de l'Information (LTCI), Institut Mines-Télécom [Paris] (IMT)-Télécom Paris-Institut Mines-Télécom [Paris] (IMT)-Télécom Paris, University of Oxford [Oxford], and Amarilli, Antoine
Subjects: FOS: Computer and information sciences, Computer Science - Logic in Computer Science, [INFO.INFO-LO] Computer Science [cs]/Logic in Computer Science [cs.LO], Theoretical computer science, General Computer Science, Computer science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Access method, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Theoretical Computer Science, [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], Computer Science - Databases, 020204 information systems, Data integrity, Schema (psychology), 0202 electrical engineering, electronic engineering, information engineering, [INFO.INFO-DB] Computer Science [cs]/Databases [cs.DB], [INFO.INFO-FL] Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], [INFO.INFO-DB]Computer Science [cs]/Databases [cs.DB], [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], Databases (cs.DB), Logic in Computer Science (cs.LO), Decidability, Pagination, 010201 computation theory & mathematics, Bounded function, Tuple
Abstract: We consider answering queries where the underlying data is available only over limited interfaces which provide lookup access to the tuples matching a given binding, but possibly restricting the number of output tuples returned. Interfaces imposing such "result bounds" are common in accessing data via the web. Given a query over a set of relations as well as some integrity constraints that relate the queried relations to the data sources, we examine the problem of deciding if the query is answerable over the interfaces; that is, whether there exists a plan that returns all answers to the query, assuming the source data satisfies the integrity constraints. The first component of our analysis of answerability is a reduction to a query containment problem with constraints. The second component is a set of "schema simplification" theorems capturing limitations on how interfaces with result bounds can be useful to obtain complete answers to queries. These results also help to show decidability for the containment problem that captures answerability, for many classes of constraints. The final component in our analysis of answerability is a "linearization" method, showing that query containment with certain guarded dependencies -- including those that emerge from answerability problems -- can be reduced to query containment for a well-behaved class of linear dependencies. Putting these components together, we get a detailed picture of how to check answerability over result-bounded services., 45 pages, 2 tables, 43 references. Complete version with proofs of the PODS'18 paper. The main text of this paper is almost identical to the PODS'18 except that we have fixed some small mistakes. Relative to the earlier arXiv version, many errors were corrected, and some terminology has changed
Published: 2018

24. Weight-based search to find clusters around medians in subspaces

Author: Sergio Peignier, Christophe Rigotti, Guillaume Beslon, Anthony Rossi, Artificial Evolution and Computational Biology (BEAGLE), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Université Lumière - Lyon 2 (UL2)-É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)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-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)-Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), Data Mining and Machine Learning (DM2L), European Project: 610427,EC:FP7:ICT,FP7-ICT-2013-10,EVOEVO(2013), Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), 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)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-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)-Centre National de la Recherche Scientifique (CNRS)-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2), Rigotti, Christophe, and Evolution of Evolution - EVOEVO - - EC:FP7:ICT2013-11-01 - 2016-10-31 - 610427 - VALID
Subjects: Computer science, business.industry, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Pattern recognition, 02 engineering and technology, Linear subspace, Facility location problem, Medoid, ComputingMethodologies_PATTERNRECOGNITION, Robustness (computer science), 020204 information systems, Outlier, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Artificial intelligence, Cluster analysis, business, Hill climbing
Abstract: International audience; There exist several clustering paradigms, leading to different techniques that are complementary in the analyst toolbox, each having its own merits and interests. Among these techniques, the K-medians approach is recognized as being robust to noise and outliers, and is an important optimization task with many different applications (e.g., facility location). In the context of subspace clustering, several paradigms have been investigated (e.g., centroid-based, cell-based), while the median-based approach has received less attention. Moreover, using standard subspace clustering outputs (e.g., centroids, medoids) there is no straightforward procedure to compute the cluster membership that optimizes the dispersion around medians. This paper advocates for the use of median-based subspace clustering as a complementary tool. Indeed, it shows that such an approach exhibits satisfactory quality clusters when compared to well-established paradigms, while medians have still their own interests depending on the user application (robustness to noise/outliers and location optimality). This paper shows that a weight-based hill climbing algorithm using a stochastic local exploration step can be sufficient to produce the clusters.
Published: 2018

25. The Stability and the Security of the Tangle

Author: Bramas, Quentin, Laboratoire des sciences de l'ingénieur, de l'informatique et de l'imagerie (ICube), École Nationale du Génie de l'Eau et de l'Environnement de Strasbourg (ENGEES)-Université de Strasbourg (UNISTRA)-Institut National des Sciences Appliquées - Strasbourg (INSA Strasbourg), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Les Hôpitaux Universitaires de Strasbourg (HUS)-Centre National de la Recherche Scientifique (CNRS)-Matériaux et Nanosciences Grand-Est (MNGE), Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Institut de Chimie du CNRS (INC)-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Institut de Chimie du CNRS (INC)-Centre National de la Recherche Scientifique (CNRS)-Réseau nanophotonique et optique, Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Centre National de la Recherche Scientifique (CNRS), Université de Strasbourg (UNISTRA), Equipe Réseaux du laboratoire ICUBE (ICUBE-Réseaux), Département Informatique du laboratoire ICUBE (ICUBE-Informatique), Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Centre National de la Recherche Scientifique (CNRS)-École Nationale du Génie de l'Eau et de l'Environnement de Strasbourg (ENGEES)-Université de Strasbourg (UNISTRA)-Institut National des Sciences Appliquées - Strasbourg (INSA Strasbourg), Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire des sciences de l'ingénieur, de l'informatique et de l'imagerie (ICube), Institut National des Sciences Appliquées - Strasbourg (INSA Strasbourg), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Strasbourg (UNISTRA)-Centre National de la Recherche Scientifique (CNRS)-École Nationale du Génie de l'Eau et de l'Environnement de Strasbourg (ENGEES)-Réseau nanophotonique et optique, Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Matériaux et nanosciences d'Alsace (FMNGE), Institut de Chimie du CNRS (INC)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS)-Institut de Chimie du CNRS (INC)-Université de Strasbourg (UNISTRA)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS), Institut de Chimie du CNRS (INC)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS)-Institut de Chimie du CNRS (INC)-Université de Strasbourg (UNISTRA)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Strasbourg (INSA Strasbourg), Institut de Chimie du CNRS (INC)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS)-Institut de Chimie du CNRS (INC)-Université de Strasbourg (UNISTRA)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire des sciences de l'ingénieur, de l'informatique et de l'imagerie (ICube), and Bramas, Quentin
Subjects: [INFO.INFO-NI] Computer Science [cs]/Networking and Internet Architecture [cs.NI], [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Distributed Ledger Technology, IOTA, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Tangle, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], [INFO.INFO-PF]Computer Science [cs]/Performance [cs.PF], Blockchain, [INFO.INFO-PF] Computer Science [cs]/Performance [cs.PF], [INFO.INFO-ET] Computer Science [cs]/Emerging Technologies [cs.ET], Security, [INFO.INFO-ET]Computer Science [cs]/Emerging Technologies [cs.ET], Stability
Abstract: In this paper we study the stability and the security of the distributed data structure at the base of the IOTA protocol, called the Tangle. The contribution of this paper is twofold. First, we present a simple model to analyze the Tangle and give the first discrete time formal analyzes of the average number of unconfirmed transactions and the average confirmation time of a transaction. Then, we define the notion of assiduous honest majority that captures the fact that the honest nodes have more hashing power than the adversarial nodes and that all this hashing power is constantly used to create transactions. This notion is important because we prove that it is a necessary assumption to protect the Tangle against double-spending attacks, and this is true for any tip selection algorithm (which is a fundamental building block of the protocol) that verifies some reasonable assumptions. In particular, the same is true with the Markov Chain Monte Carlo selection tip algorithm currently used in the IOTA protocol. Our work shows that either all the honest nodes must constantly use all their hashing power to validate the main chain (similarly to the Bitcoin protocol) or some kind of authority must be provided to avoid this kind of attack (like in the current version of the IOTA where a coordinator is used). The work presented here constitute a theoretical analysis and cannot be used to attack the current IOTA implementation. The goal of this paper is to present a formalization of the protocol and, as a starting point, to prove that some assumptions are necessary in order to defend the system again double-spending attacks. We hope that it will be used to improve the current protocol with a more formal approach., OASIcs, Vol. 71, International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2019), pages 8:1-8:15
Published: 2018

26. Fixing improper colorings of graphs

Author: Garnero, Valentin, Junosza-Szaniawski, Konstanty, Liedloff, Mathieu, Montealegre, Pedro, Rzążewski, Paweł, Liedloff, Mathieu, Laboratoire d'Informatique Fondamentale d'Orléans (LIFO), Université d'Orléans (UO)-Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA), Faculty of Mathematics and Information Science [Warszawa], Warsaw University of Technology [Warsaw], Ecole Nationale Supérieure d'Ingénieurs de Bourges-Université d'Orléans (UO), Institute for Computer Science and Control [Budapest] (SZTAKI), and Hungarian Academy of Sciences (MTA)
Subjects: FOS: Computer and information sciences, Discrete Mathematics (cs.DM), [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], ComputingMilieux_MISCELLANEOUS, Computer Science - Discrete Mathematics
Abstract: In this paper we consider a variation of a recoloring problem, called the Color-Fixing. Let us have some non-proper $r$-coloring $\varphi$ of a graph $G$. We investigate the problem of finding a proper $r$-coloring of $G$, which is "the most similar" to $\varphi$, i.e. the number $k$ of vertices that have to be recolored is minimum possible. We observe that the problem is NP-complete for any $r \geq 3$, even for bipartite planar graphs. On the other hand, the problem is fixed-parameter tractable, when parameterized by the number of allowed transformations $k$. We provide an $2^n \cdot n^{\mathcal{O}(1)}$ algorithm for the problem (for any fixed $r$) and a linear algorithm for graphs with bounded treewidth. We also show several lower complexity bounds, using standard complexity assumptions. Finally, we investigate the {\em fixing number} of a graph $G$. It is the maximum possible distance (in the number of transformations) between some non-proper coloring of $G$ and a proper one., Comment: An extended abstract of this paper was presented on the conference SOFSEM 2015
Published: 2018

27. Complexity of Grundy coloring and its variants

Author: Eun Jung Kim, Florian Sikora, Florent Foucaud, Édouard Bonnet, Bonnet, Édouard, 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), Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes (LIMOS), SIGMA Clermont (SIGMA Clermont)-Université d'Auvergne - Clermont-Ferrand I (UdA)-Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Blaise Pascal - Clermont-Ferrand 2 (UBP), Institute for Computer Science and Control [Budapest] (SZTAKI), Hungarian Academy of Sciences (MTA), Modèles de calcul, Complexité, Combinatoire (MC2), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), and Université Blaise Pascal - Clermont-Ferrand 2 (UBP)-Université d'Auvergne - Clermont-Ferrand I (UdA)-SIGMA Clermont (SIGMA Clermont)-Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)
Subjects: FOS: Computer and information sciences, [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Computational complexity theory, Discrete Mathematics (cs.DM), [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION, Parameterized complexity, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, [INFO] Computer Science [cs], 01 natural sciences, Combinatorics, Greedy coloring, Grundy number, Chordal graph, Computer Science - Data Structures and Algorithms, FOS: Mathematics, Discrete Mathematics and Combinatorics, Mathematics - Combinatorics, Data Structures and Algorithms (cs.DS), Grundy coloring, [INFO]Computer Science [cs], 0101 mathematics, Mathematics, ComputingMethodologies_COMPUTERGRAPHICS, Exponential time hypothesis, Mathematics::Combinatorics, Applied Mathematics, 010102 general mathematics, Exact algorithm, Interval graph, Connected Grundy, Complexity, Vertex (geometry), Treewidth, Computational complexity, 010201 computation theory & mathematics, Bipartite graph, Weak Grundy, [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC], Combinatorics (math.CO), Computer Science - Discrete Mathematics, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: The Grundy number of a graph is the maximum number of colors used by the greedy coloring algorithm over all vertex orderings. In this paper, we study the computational complexity of GRUNDY COLORING, the problem of determining whether a given graph has Grundy number at least $k$. We also study the variants WEAK GRUNDY COLORING (where the coloring is not necessarily proper) and CONNECTED GRUNDY COLORING (where at each step of the greedy coloring algorithm, the subgraph induced by the colored vertices must be connected). We show that GRUNDY COLORING can be solved in time $O^*(2.443^n)$ and WEAK GRUNDY COLORING in time $O^*(2.716^n)$ on graphs of order $n$. While GRUNDY COLORING and WEAK GRUNDY COLORING are known to be solvable in time $O^*(2^{O(wk)})$ for graphs of treewidth $w$ (where $k$ is the number of colors), we prove that under the Exponential Time Hypothesis (ETH), they cannot be solved in time $O^*(2^{o(w\log w)})$. We also describe an $O^*(2^{2^{O(k)}})$ algorithm for WEAK GRUNDY COLORING, which is therefore $\fpt$ for the parameter $k$. Moreover, under the ETH, we prove that such a running time is essentially optimal (this lower bound also holds for GRUNDY COLORING). Although we do not know whether GRUNDY COLORING is in $\fpt$, we show that this is the case for graphs belonging to a number of standard graph classes including chordal graphs, claw-free graphs, and graphs excluding a fixed minor. We also describe a quasi-polynomial time algorithm for GRUNDY COLORING and WEAK GRUNDY COLORING on apex-minor graphs. In stark contrast with the two other problems, we show that CONNECTED GRUNDY COLORING is $\np$-complete already for $k=7$ colors., Comment: 24 pages, 7 figures. This version contains some new results and improvements. A short paper based on version v2 appeared in COCOON'15
Published: 2018

28. Fine-grained complexity of coloring unit disks and balls

Author: Biró, Csaba, Bonnet, Édouard, Marx, Dániel, Miltzow, Tillmann, Rzazewski, Pawel, Modèles de calcul, Complexité, Combinatoire (MC2), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Computer and Automation Research Institute [Budapest] (MTA SZTAKI ), Faculty of Mathematics and Information Science [Warszawa], Warsaw University of Technology [Warsaw], École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), University of Louisville, Katz, MJ, Aronov, B, and Bonnet, Édouard
Subjects: [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], 000 Computer science, knowledge, general works, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány, 0102 computer and information sciences, 02 engineering and technology, [INFO] Computer Science [cs], [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], 01 natural sciences, ACM: G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS/G.2.2: Graph Theory, [INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG], ACM: F.: Theory of Computation/F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY/F.2.2: Nonnumerical Algorithms and Problems, 010201 computation theory & mathematics, Computer Science, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC], [INFO]Computer Science [cs]
Abstract: On planar graphs, many classic algorithmic problems enjoy a certain ``square root phenomenon'' and can be solved significantly faster than what is known to be possible on general graphs: for example, Independent Set, 3-Coloring, Hamiltonian Cycle, Dominating Set can be solved in time $2^{O(\sqrt{n})}$ on an $n$-vertex planar graph, while no $2^{o(n)}$ algorithms exist for general graphs, assuming the Exponential Time Hypothesis (ETH). The square root in the exponent seems to be best possible for planar graphs: assuming the ETH, the running time for these problems cannot be improved to $2^{o(\sqrt{n})}$. In some cases, a similar speedup can be obtained for 2-dimensional geometric problems, for example, there are $2^{O(\sqrt{n}\log n)}$ time algorithms for Independent Set on unit disk graphs or for TSP on 2-dimensional point sets. In this paper, we explore whether such a speedup is possible for geometric coloring problems. On the one hand, geometric objects can behave similarly to planar graphs: 3-Coloring can be solved in time $2^{O(\sqrt{n})}$ on the intersection graph of $n$ disks in the plane and, assuming the ETH, there is no such algorithm with running time $2^{o(\sqrt{n})}$. On the other hand, if the number $\ell$ of colors is part of the input, then no such speedup is possible: Coloring the intersection graph of $n$ unit disks with $\ell$ colors cannot be solved in time $2^{o(n)}$, assuming the ETH. More precisely, we exhibit a smooth increase of complexity as the number $\ell$ of colors increases: If we restrict the number of colors to $\ell=\Theta(n^{\alpha})$ for some $0\le \alpha\le 1$, then the problem of coloring the intersection graph of $n$ disks with $\ell$ colors • can be solved in time $\exp \left( O(n^{\frac{1+\alpha}{2}}\log n) \right)=\exp \left( O(\sqrt{n\ell}\log n) \right)$, and • cannot be solved in time $\exp \left ( o(n^{\frac{1+\alpha}{2}})\right )=\exp \left( o(\sqrt{n\ell}) \right)$, even on unit disks, unless the ETH fails. More generally, we consider the problem of coloring $d$-dimensional balls in the Euclidean space and obtain analogous results showing that the problem • can be solved in time $\exp \left( O(n^{\frac{d-1+\alpha}{d}}\log n) \right)$ $=\exp \left( O(n^{1-1/d}\ell^{1/d}\log n) \right)$, and • cannot be solved in time $\exp \left(O(n^{\frac{d-1+\alpha}{d}-\epsilon})\right)= \exp \left(O(n^{1-1/d-\epsilon}\ell^{1/d})\right)$ for any $\epsilon>0$, even for unit balls, unless the ETH fails. Finally, we prove that fatness is crucial to obtain subexponential algorithms for coloring. We show that existence of an algorithm coloring an intersection graph of segments using a constant number of colors in time $2^{o(n)}$ already refutes the ETH., Journal of Computational Geometry, Vol. 9 No. 2 (2018): Special Issue of Selected Papers from SoCG 2017
Published: 2018

29. IEEE eHPWAS'17: Fifth international IEEE workshop on e-health pervasive wireless applications and services 2017

Author: Lemlouma, Tayeb, Rachedi, Abderrezak, Laborie, Sébastien, António, Santos, Vasilakos, Athanasios, Lemlouma, Tayeb, IEEE, Abderrahim Benslimane, RÉSEAUX, TÉLÉCOMMUNICATION ET SERVICES (IRISA-D2), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Laboratoire d'Informatique Gaspard-Monge (LIGM), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), Laboratoire Informatique de l'Université de Pau et des Pays de l'Adour (LIUPPA), Université de Pau et des Pays de l'Adour (UPPA), Fraunhofer Center for Assistive Information and Communication Solutions [Porto] (Fraunhofer AICOS), Fraunhofer (Fraunhofer-Gesellschaft), Luleå University of Technology (LUT), Tayeb Lemlouma, Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes 1 (UR1), Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-CentraleSupélec-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Bretagne Sud (UBS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), and Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique)
Subjects: [INFO.INFO-AI] Computer Science [cs]/Artificial Intelligence [cs.AI], E-health, Service, [INFO.INFO-NI] Computer Science [cs]/Networking and Internet Architecture [cs.NI], [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO] Computer Science [cs], [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], Networking, [INFO.EIAH] Computer Science [cs]/Technology for Human Learning, Wireless, [INFO]Computer Science [cs], [INFO.EIAH]Computer Science [cs]/Technology for Human Learning, Smart environments, Pervasive
Abstract: International audience; The fifth international IEEE workshop on e-Health Pervasive Wireless Applications and Services e-HPWAS'17 (in conjunction with the 13h IEEE WiMob conference) targets providing optimal, secured and context aware e-health services with the best quality of services (QoS) and user’s experience (QoE). Applications and services are considered in wireless environments and architecture with the use of IoT (Internet of things), big data analysis and a strong heterogeneity of the used access technologies, sensors, terminals, users’ needs and services (data, content, live streams or complex network services). Emerging e-Health services and applications can involve the use of “heavy” content such as multimedia content and streams (e.g. 3D-TV, media conferencing, remote live diagnostics) using conventional e-health devices but also using terminals like smart TV sets, home-boxes, smartphones and tablets. The considered issues of e-HPWAS are related to e-Health care and safety services provided for patients, elderly and dependent persons. These services are generally built using different communication technologies, for different profiles of people and in different contexts and places (e.g. in health institutions, at home, in the city). Provided services should, ideally, be accessible anytime, anywhere and using any kind of device or platform.eHPWAS encourages the submission of original works describing research results, practical or industrial e-health solutions. Papers describing advanced prototypes, platforms, techniques and general survey for discussing future perspectives and directions are also encouraged. CALL FOR PAPERS >> All accepted papers will be published in the 13h IEEE WiMob WiMob proceedings published by IEEE, and will be accessible via IEEE Xplore Digital Library and indexed by DBLP. The workshops will be held in Rome, Italy - October 9, 2017. A selection of accepted papers of high quality will be considered and authors will be invited to produce an extended version to be published in a special issue of a specialized journal.
Published: 2017

30. Parameterized Resiliency Problems via Integer Linear Programming

Author: Jason Crampton, Rémi Watrigant, Martin Koutecký, Gregory Gutin, and Watrigant, Remi
Subjects: FOS: Computer and information sciences, Mathematical optimization, 021103 operations research, Computer science, 0211 other engineering and technologies, Parameterized complexity, Parameterized algorithms, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, Decision problem, Computational Complexity (cs.CC), [INFO] Computer Science [cs], 01 natural sciences, Computer Science - Computational Complexity, 010201 computation theory & mathematics, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), Parametric linear programming, Integer programming, ComputingMilieux_MISCELLANEOUS
Abstract: We introduce an extension of decision problems called resiliency problems. In resiliency problems, the goal is to decide whether an instance remains positive after any (appropriately defined) perturbation has been applied to it. To tackle these kinds of problems, some of which might be of practical interest, we introduce a notion of resiliency for Integer Linear Programs (ILP) and show how to use a result of Eisenbrand and Shmonin (Math. Oper. Res., 2008) on Parametric Linear Programming to prove that ILP Resiliency is fixed-parameter tractable (FPT) under a certain parameterization. To demonstrate the utility of our result, we consider natural resiliency versions of several concrete problems, and prove that they are FPT under natural parameterizations. Our first results concern a four-variate problem which generalizes the Disjoint Set Cover problem and which is of interest in access control. We obtain a complete parameterized complexity classification for every possible combination of the parameters. Then, we introduce and study a resiliency version of the Closest String problem, for which we extend an FPT result of Gramm et al. (Algorithmica, 2003). We also consider problems in the fields of scheduling and social choice. We believe that many other problems can be tackled by our framework., Comment: This paper is based on two papers published in conference proceedings of AAIM 2016 and CIAC 2017
Published: 2017

31. Complexity of Edge Monitoring on Some Graph Classes

Author: Bagan, Guillaume, Beggas, Fairouz, Haddad, Mohammed, Kheddouci, Hamamache, Graphes, AlgOrithmes et AppLications (GOAL), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), 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)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Université Lumière - Lyon 2 (UL2), and Haddad, Mohammed
Subjects: FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Applied Mathematics, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Discrete Mathematics and Combinatorics, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Computer Science - Discrete Mathematics, MathematicsofComputing_DISCRETEMATHEMATICS
Abstract: In this paper, we study the complexity of the edge monitoring problem. A vertex $v$ monitors an edge $e$ if both extremities together with $v$ form a triangle in the graph. Given a graph $G=(V,E)$ and a weight function on edges $c$ where $c(e)$ is the number of monitors that needs the edge $e$, the problem is to seek a minimum subset of monitors $S$ such that every edge $e$ in the graph is monitored by at least $c(e)$ vertices in $S$. In this paper, we study the edge monitoring problem on several graph classes such as complete graphs, block graphs, cographs, split graphs, interval graphs and planar graphs. We also generalize the problem by adding weights on vertices.
Published: 2017
Full Text: View/download PDF

32. Optimizing egalitarian performance in the side-effects model of colocation for data center resource management

Author: Fanny Pascual, Krzysztof Rzadca, Pascual, Fanny, Recherche Opérationnelle (RO), Laboratoire d'Informatique de Paris 6 (LIP6), Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre et Marie Curie - Paris 6 (UPMC)-Centre National de la Recherche Scientifique (CNRS), Warsaw University of Technology [Warsaw], PHC POLONIUM 2017 (project 35396ZB), Institute of Informatics [Warsaw], Faculty of Mathematics, Informatics, and Mechanics [Warsaw] (MIMUW), and University of Warsaw (UW)-University of Warsaw (UW)
Subjects: FOS: Computer and information sciences, [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], [INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO], Computer science, Distributed computing, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Cloud computing, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 02 engineering and technology, [INFO] Computer Science [cs], Scheduling (computing), 020204 information systems, 0202 electrical engineering, electronic engineering, information engineering, [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Resource management, [INFO]Computer Science [cs], scheduling, approximation algorithm, business.industry, cloud computing, Approximation algorithm, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], 020202 computer hardware & architecture, Computer Science - Distributed, Parallel, and Cluster Computing, Combinatorial optimization, Data center, [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC], Distributed, Parallel, and Cluster Computing (cs.DC), [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], heterogeneity, business, complexity
Abstract: In data centers, up to dozens of tasks are colocated on a single physical machine. Machines are used more efficiently, but tasks' performance deteriorates, as colocated tasks compete for shared resources. As tasks are heterogeneous, the resulting performance dependencies are complex. In our previous work [18] we proposed a new combinatorial optimization model that uses two parameters of a task - its size and its type - to characterize how a task influences the performance of other tasks allocated to the same machine. In this paper, we study the egalitarian optimization goal: maximizing the worst-off performance. This problem generalizes the classic makespan minimization on multiple processors (P||Cmax). We prove that polynomially-solvable variants of multiprocessor scheduling are NP-hard and hard to approximate when the number of types is not constant. For a constant number of types, we propose a PTAS, a fast approximation algorithm, and a series of heuristics. We simulate the algorithms on instances derived from a trace of one of Google clusters. Algorithms aware of jobs' types lead to better performance compared with algorithms solving P||Cmax. The notion of type enables us to model degeneration of performance caused by using standard combinatorial optimization methods. Types add a layer of additional complexity. However, our results - approximation algorithms and good average-case performance - show that types can be handled efficiently., Author's version of a paper published in Euro-Par 2017 Proceedings, extends the published paper with addtional results and proofs
Published: 2017

33. Trading performance for memory in sparse direct solvers using low-rank compression

Author: Grégoire PICHON, Thibault Marette, Loris Marchal, Frédéric Vivien, Optimisation des ressources : modèles, algorithmes et ordonnancement (ROMA), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Inria Lyon, Institut National de Recherche en Informatique et en Automatique (Inria), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), École normale supérieure de Lyon (ENS de Lyon), ANR-19-CE46-0009,SOLHARIS,Solveurs pour architectures hétérogènes utilisant des supports d'exécution, objectif scalabilité(2019), 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)-Laboratoire de l'Informatique du Parallélisme (LIP), Université de Lyon-Université de Lyon-Centre National de la Recherche Scientifique (CNRS), This work is part of the SOLHARIS project, supported by the Agence Nationale de la Recherche, under grant ANR-19-CE46-0009., INRIA, ANR-18-CE46-0006,SaSHiMi,Solveur linéaire creux exploitant des matrices hierarchiques(2018), Roma, Equipe, Solveurs pour architectures hétérogènes utilisant des supports d'exécution, objectif scalabilité - - SOLHARIS2019 - ANR-19-CE46-0009 - AAPG2019 - VALID, APPEL À PROJETS GÉNÉRIQUE 2018 - Solveur linéaire creux exploitant des matrices hierarchiques - - SaSHiMi2018 - ANR-18-CE46-0006 - AAPG2018 - VALID, École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-École normale supérieure - Lyon (ENS Lyon)-Université Claude Bernard Lyon 1 (UCBL), École normale supérieure - Lyon (ENS Lyon), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon)-Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), and Université de Lyon-École normale supérieure - Lyon (ENS Lyon)
Subjects: [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Contraintes mémoire, Computer Networks and Communications, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 010103 numerical & computational mathematics, [INFO] Computer Science [cs], [INFO.INFO-NA]Computer Science [cs]/Numerical Analysis [cs.NA], Solveurs directs creux, 01 natural sciences, 010101 applied mathematics, Compression Low-rank, low-rank compression, Hardware and Architecture, [INFO.INFO-NA] Computer Science [cs]/Numerical Analysis [cs.NA], Ordonnancement, [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC], [INFO]Computer Science [cs], scheduling, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], 0101 mathematics, sparse direct solvers, memory constraints, Software
Abstract: Sparse direct solvers using Block Low-Rank compression have been proven efficient to solve problems arising in many real-life applications. Improving those solvers is crucial for being able to 1) solve larger problems and 2) speed up computations. A main characteristic of a sparse direct solver using low-rank compression is when compression is performed. There are two distinct approaches: (1) all blocks are compressed before starting the factorization, which reduces the memory as much as possible, or (2) each block is compressed as late as possible, which usually leads to better speedup. The objective of this paper is to design a composite approach, to speedup computations while staying under a given memory limit. This should allow to solve large problems that cannot be solved with Approach 2 while reducing the execution time compared to Approach 1.We propose a memory-aware strategy where each block can be compressed either at the beginning or as late as possible. We first consider the problem of choosing when to compress each block, under the assumption that all information on blocks is perfectly known, i.e., memory requirement and execution time of a block when compressed or not. We show that this problem is a variant of the NP-complete Knapsack problem, and adapt an existing 2-approximation algorithm for our problem. Unfortunately, the required information on blocks depends on numerical properties and in practice cannot be known in advance. We thus introduce models to estimate those values. Experiments on the PaStiX solver demonstrate that our new approach can achieve an excellent trade-off between memory consumption and computational cost. For instance on matrix Geo1438, Approach 2 uses three times as much memory as Approach 1 while being three times faster. Our new approach leads to an execution time only 30% larger than Approach 2 when given a memory 30% larger than the one needed by Approach 1., Les solveurs directs creux utilisant de la compression low-rank ont montré leur efficacité pour résoudre de grands systèmes. Les améliorer permetde 1) résoudre de plus grands problèmes et 2) accélérer la résolution. Une caractéristique principale de ces solveurs est quand la compression est réalisée. Il existe deux approches: (1) tous les blocs sont compressés avant le début de la factorisation, ce qui minimise la consommation mémoire, ou (2) chaque bloc est compressé au plus tard, ce qui permet d’avoir de meilleures performances. L’objectif de cet article est de proposer une approche intermédiaire, qui accélère les calculs au maximum tout en restant en dessous d’une limite mémoire donnée. Cela devrait permettre de résoudre de grands problèmes que l’approche 2 ne peut pas résoudre ou de réduire le temps d’exécution de l’approche 1. Nous proposonsune stratégie memory-aware où chaque bloc peut ˆêtre compressé au début ou au plus tard. Nous commençons par considérer le problème où toutes les informations (consommation mémoire et temps d’exécution en version compressée ou non) sont parfaitement connues. Nous montrons que ce problème est une variante du problème NP-complet Knapsack et adaptons une 2-approximation pour notre problème. Malheureusement, toutes ces informations dépendent de propriétés numériques et ne sont pas connues `a l’avance. Des modèles sont donc introduits afin d’estimer ces valeurs. Des expérimentations avec le solveur PaStiX montrent que notre approche permet d’avoir un excellent compromis entre consommation mémoire et temps d’exécution. Par exemple, pour la matrice Geo1438, l’approche 2 utilise trois fois plus de mémoire que l’approche 1, qui est trois fois plus lente. Notre nouvelle méthode permet d’obtenir à la fois un temps d’exécution seulement 30% supérieur à celui de l’approche 2 tout en ayant une consommation mémoire seulement supérieure de 30% à celle de l’approche 1.
Published: 2022

34. Shrinking Maxima, Decreasing Costs: New Online Packing and Covering Problems

Author: Magnús M. Halldórsson, Dror Rawitz, Adi Rosén, Boaz Patt-Shamir, Pierre Fraigniaud, Networks, Graphs and Algorithms (GANG), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), 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), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), School of Computer Science [Reykjavik], Reykjavík University, Department of Electrical Engineering, Tel Aviv University [Tel Aviv], School of Computer Science (TAU-CS), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), 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, Fraigniaud, Pierre, and Tel Aviv University (TAU)
Subjects: Mathematical optimization, General Computer Science, Competitive analysis, Applied Mathematics, 010102 general mathematics, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Covering problems, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 01 natural sciences, Upper and lower bounds, Computer Science Applications, 010104 statistics & probability, Packing problems, Set packing, 010201 computation theory & mathematics, Knapsack problem, [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], 0101 mathematics, Online algorithm, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Mathematics, Integer (computer science)
Abstract: International audience; Weconsidertwonewvariantsofonlineintegerprogramsthatareduals.In the packing problem we are given a set of items and a collection of knapsack constraints over these items that are revealed over time in an online fashion. Upon arrival of a constraint we may need to remove several items (irrevocably) so as to maintain feasibility of the solution. Hence, the set of packed items becomes smaller over time. The goal is to maximize the number, or value, of packed items. The problem originates from a buffer-overflow model in communication networks, where items represent information units broken into multiple packets. The other problem considered is online covering: there is a universe to be covered. Sets arrive online, and we must decide for each set whether we add it to the cover or give it up. The cost of a solution is the total cost of sets taken, plus a penalty for each uncovered element. The number of sets in the solution grows over time, but its cost goes down. This problem is motivated by team formation, where the universe consists of skills, and sets represent candidates we may hire. The packing problem was introduced in Emek et al. (SIAM J Comput 41(4):728–746, 2012) for the special case where the matrix is binary; in this paper we extend the solution to general matrices with non-negative integer entries. The covering problem is introduced in this paper; we present matching upper and lower bounds on its competitive ratio.
Published: 2016

35. A Message-Passing and Adaptive Implementation of the Randomized Test-and-Set Object

Author: Emmanuelle Anceaume, Achour Mostefaoui, Bruno Sericola, François Castella, Confidentialité, Intégrité, Disponibilité et Répartition (CIDRE), CentraleSupélec-Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-Centre National de la Recherche Scientifique (CNRS), Institut de Recherche Mathématique de Rennes (IRMAR), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-École normale supérieure - Rennes (ENS Rennes)-Université de Rennes 2 (UR2)-Centre National de la Recherche Scientifique (CNRS)-INSTITUT AGRO Agrocampus Ouest, Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro), Invariant Preserving SOlvers (IPSO), Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), LINA, Université de Nantes (UN), Dependability Interoperability and perfOrmance aNalYsiS Of networkS (DIONYSOS), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-RÉSEAUX, TÉLÉCOMMUNICATION ET SERVICES (IRISA-D2), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), ANR-11-INSE-010, Avresky, DR, Busnel Y., ANR-11-INSE-0010,MARS,Systèmes embarqués fiables et faible consommation à base de Mémoires Magnétiques (MRAM)(2011), CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA), AGROCAMPUS OUEST, Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Institut national d'enseignement supérieur pour l'agriculture, l'alimentation et l'environnement (Institut Agro)-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Université de Rennes 2 (UR2), Université de Rennes (UNIV-RENNES)-École normale supérieure - Rennes (ENS Rennes)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-AGROCAMPUS OUEST, Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Inria Rennes – Bretagne Atlantique, Confidentialité, Intégrité, Disponibilité et Répartition ( CIDRE ), Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -SYSTÈMES LARGE ÉCHELLE ( IRISA-D1 ), Institut de Recherche en Informatique et Systèmes Aléatoires ( IRISA ), CentraleSupélec-Université de Rennes 1 ( UR1 ), Université de Rennes ( UNIV-RENNES ) -Université de Rennes ( UNIV-RENNES ) -Télécom Bretagne-Institut National des Sciences Appliquées ( INSA ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -École normale supérieure - Rennes ( ENS Rennes ) -Centre National de la Recherche Scientifique ( CNRS ) -Université de Bretagne Sud ( UBS ) -CentraleSupélec-Université de Rennes 1 ( UR1 ), Université de Rennes ( UNIV-RENNES ) -Université de Rennes ( UNIV-RENNES ) -Télécom Bretagne-Institut National des Sciences Appliquées ( INSA ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -École normale supérieure - Rennes ( ENS Rennes ) -Centre National de la Recherche Scientifique ( CNRS ) -Université de Bretagne Sud ( UBS ) -Institut de Recherche en Informatique et Systèmes Aléatoires ( IRISA ), Université de Rennes ( UNIV-RENNES ) -Université de Rennes ( UNIV-RENNES ) -Télécom Bretagne-Institut National des Sciences Appliquées ( INSA ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -École normale supérieure - Rennes ( ENS Rennes ) -Centre National de la Recherche Scientifique ( CNRS ) -Université de Bretagne Sud ( UBS ) -Université de Rennes 1 ( UR1 ), Université de Rennes ( UNIV-RENNES ) -Université de Rennes ( UNIV-RENNES ) -Télécom Bretagne-Institut National des Sciences Appliquées ( INSA ) -École normale supérieure - Rennes ( ENS Rennes ) -Centre National de la Recherche Scientifique ( CNRS ) -Université de Bretagne Sud ( UBS ), Institut de Recherche Mathématique de Rennes ( IRMAR ), Université de Rennes 1 ( UR1 ), Université de Rennes ( UNIV-RENNES ) -Université de Rennes ( UNIV-RENNES ) -AGROCAMPUS OUEST-École normale supérieure - Rennes ( ENS Rennes ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National des Sciences Appliquées ( INSA ) -Université de Rennes 2 ( UR2 ), Université de Rennes ( UNIV-RENNES ) -Centre National de la Recherche Scientifique ( CNRS ), Invariant Preserving SOlvers ( IPSO ), Université de Rennes ( UNIV-RENNES ) -Centre National de la Recherche Scientifique ( CNRS ) -Université de Rennes 1 ( UR1 ), Université de Rennes ( UNIV-RENNES ) -Centre National de la Recherche Scientifique ( CNRS ) -Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique ( Inria ), Université de Nantes ( UN ), Dependability Interoperability and perfOrmance aNalYsiS Of networkS ( DIONYSOS ), Institut National de Recherche en Informatique et en Automatique ( Inria ) -Institut National de Recherche en Informatique et en Automatique ( Inria ) -RÉSEAUX, TÉLÉCOMMUNICATION ET SERVICES ( IRISA-D2 ), ANR-11-INSE-010,AMORES, SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Anceaume, Emmanuelle, and ANR-11-LABX-0020,LEBESGUE,Centre de Mathématiques Henri Lebesgue : fondements, interactions, applications et Formation(2011)
Subjects: [ INFO ] Computer Science [cs], Computer science, Distributed computing, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], asynchronous message-passing system, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, [INFO] Computer Science [cs], Test-and-set, 01 natural sciences, randomized algorithm, Set (abstract data type), [ INFO.INFO-DC ] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Synchronization (computer science), [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], 0202 electrical engineering, electronic engineering, information engineering, [INFO]Computer Science [cs], [ INFO.INFO-DS ] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Shared memory model, crash failures, [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], agreement problem, Message passing, 020207 software engineering, Object (computer science), [ INFO.INFO-GT ] Computer Science [cs]/Computer Science and Game Theory [cs.GT], Memory management, 010201 computation theory & mathematics, Asynchronous communication, Test set, [INFO.INFO-GT] Computer Science [cs]/Computer Science and Game Theory [cs.GT], Test&Set, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], synchronization
Abstract: —This paper presents a solution to the well-known Test&Set operation in an asynchronous system prone to process crashes. Test&Set is a synchronization operation that, when invoked by a set of processes, returns yes to a unique process and returns no to all the others. Recently many advances in implementing Test&Set objects have been achieved, however all of them uniquely target the shared memory model. In this paper we propose an implementation of a Test&Set object for a message passing distributed system. This implementation can be invoked by any number p
Published: 2015

36. Integrating Domain-Based Features into Event-B: a Nose Gear Velocity Case Study

Author: Anton Tarasyuk, Dominique Méry, Rushikesh Sawant, Modeling and Verification of Distributed Algorithms and Systems (VERIDIS), Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Université de Lorraine (UL), TELECOM Nancy, Proof-oriented development of computer-based systems (MOSEL), Department of Formal Methods (LORIA - FM), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Turku Centre for Computer Science, University of Turku, Ladjel Bellatreche, Yannis Manolopoulos, ANR-13-INSE-0001,IMPEX,Intégration des sémantiques implicite et explicite dans les développements de systèmes discrets fondés sur la preuve.(2013), Åbo Akademi University [Turku]-University of Turku, Méry, Dominique, Ingénierie Numérique et Sécurité - Intégration des sémantiques implicite et explicite dans les développements de systèmes discrets fondés sur la preuve. - - IMPEX2013 - ANR-13-INSE-0001 - INS - VALID, Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Max-Planck-Institut für Informatik (MPII), Max-Planck-Gesellschaft-Max-Planck-Gesellschaft, and Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)
Subjects: [INFO.INFO-AI] Computer Science [cs]/Artificial Intelligence [cs.AI], implicit semantics, explicit semantics nose gear velocity, Theoretical computer science, [INFO.INFO-LO] Computer Science [cs]/Logic in Computer Science [cs.LO], Computer science, Process (engineering), Semantics (computer science), [INFO.INFO-SE] Computer Science [cs]/Software Engineering [cs.SE], [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-SE]Computer Science [cs]/Software Engineering [cs.SE], System model, Domain (software engineering), [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], modelling, [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], Application domain, refinement, formal method, Simulation, [INFO.INFO-FL] Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], Event (computing), [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], Formal methods, ACM: F.: Theory of Computation, Domain knowledge, Event-B
Abstract: International audience; This paper presents the formal modelling of a nose gear velocity system, a software-based system for estimating the ground velocity of an aircraft. We employ the Event-B modelling language to conduct this case study. Event-B allows us to construct and verify the formal model of the system using the incremental refinement-based process. The main goal of the case study is to highlight the need for separating and integrating explicit semantics of application domain into the formal development process. Traditionally in Event-B development, domain descriptions of systems containing domain knowledge are treated as second-class citizens, and the modelling is implicit and usually distributed between the requirements model and the system model. In this paper, we highlight the need for explicit modelling of domain contexts as first-class citizens, and we illustrate concepts related to implicit and explicit semantics with the help of an example in Event-B.
Published: 2015

37. The Minimum Substring Cover problem

Author: Romeo Rizzi, Dror Rawitz, Stéphane Vialette, Danny Hermelin, Laboratoire d'Informatique Gaspard-Monge (LIGM), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), Kaklamanis Christos and Skutella Martin, Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), and Vialette, Stéphane
Subjects: [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Concatenation, Vertex cover, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, local-ratio technique, 01 natural sciences, Substring Cover, Theoretical Computer Science, computational biology, 0202 electrical engineering, electronic engineering, information engineering, Randomized rounding, ComputingMilieux_MISCELLANEOUS, Mathematics, Discrete mathematics, Approximation algorithm, Set cover problem, Dictionary Generation, Approximation algorithms, Substring, Computer Science Applications, formal language theory, linear programming rounding, Computational Theory and Mathematics, Local-ratio, 010201 computation theory & mathematics, Cutting stock problem, approximation algorithms, 020201 artificial intelligence & image processing, Computational problem, Information Systems
Abstract: In this paper we consider the problem of covering a set of strings S with a set C of substrings in S, where C is said to cover S if every string in S can be written as a concatenation of the substrings in C. We discuss applications for the problem that arise in the context of computational biology and formal language theory. We then proceed to show that this problem is at least as hard as the MINIMUM SET COVER problem. In the main part of the paper, we focus on devising approximation algorithms for the problem using two generic paradigms - the local-ratio technique and linear programming rounding.
Published: 2008

38. Dimensionality Reduction for Persistent Homology with Gaussian Kernels

Author: Boissonnat, Jean-Daniel, Dutta, Kunal, Understanding the Shape of Data (DATASHAPE), 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)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria), Faculty of Mathematics, Informatics, and Mechanics [Warsaw] (MIMUW), University of Warsaw (UW), ANR-19-P3IA-0002,3IA@cote d'azur,3IA Côte d'Azur(2019), Boissonnat, Jean-Daniel, and 3IA Côte d'Azur - - 3IA@cote d'azur2019 - ANR-19-P3IA-0002 - P3IA - VALID
Subjects: Computational Geometry (cs.CG), FOS: Computer and information sciences, [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], General Topology (math.GN), [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], [MATH.MATH-AT] Mathematics [math]/Algebraic Topology [math.AT], [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], [INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG], [MATH.MATH-AT]Mathematics [math]/Algebraic Topology [math.AT], FOS: Mathematics, Computer Science - Computational Geometry, [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC], Mathematics - General Topology
Abstract: Computing persistent homology using Gaussian kernels is useful in the domains of topological data analysis and machine learning as shown by Phillips, Wang and Zheng [SoCG 2015]. However, contrary to the case of computing persistent homology using the Euclidean distance or even the $k$-distance, it is not known how to compute the persistent homology of high dimensional data using Gaussian kernels. In this paper, we consider a power distance version of the Gaussian kernel distance (GKPD) given by Phillips, Wang and Zheng, and show that the persistent homology of the \v{C}ech filtration of $P$ computed using the GKPD is approximately preserved. For datasets in $d$-dimensional Euclidean space, under a relative error bound of $\varepsilon \in [0,1]$, we obtain a dimensionality of $(i)$ $O(\varepsilon^{-2}\log^2 n)$ for $n$-point datasets and $(ii)$ $O(D\varepsilon^{-2}\log (Dr/\varepsilon))$ for datasets having diameter $r$ (up to a scaling factor). We use two main ingredients. The first one is a new decomposition of the squared radii of \v{C}ech simplices using the kernel power distance, in terms of the pairwise GKPDs between the vertices, which we state and prove. The second one is the Random Fourier Features (RFF) map of Rahimi and Recht [NeurIPS 2007], as used by Chen and Phillips [ALT 2017].
Published: 2023

39. Graph edit distance : a new binary linear programming formulation

Author: Lerouge, Julien, Abu-Aisheh, Zeina, Raveaux, Romain, Héroux, Pierre, Adam, Sébastien, Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes (LITIS), Université Le Havre Normandie (ULH), Normandie Université (NU)-Normandie Université (NU)-Université de Rouen Normandie (UNIROUEN), Normandie Université (NU)-Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA), Equipe Apprentissage (DocApp - LITIS), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA)-Université Le Havre Normandie (ULH), Laboratoire d'Informatique Fondamentale et Appliquée de Tours (LIFAT), Université de Tours (UT)-Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), Raveaux, Romain, Centre National de la Recherche Scientifique (CNRS)-Université de Tours-Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL), and Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)
Subjects: FOS: Computer and information sciences, [INFO.INFO-CV] Computer Science [cs]/Computer Vision and Pattern Recognition [cs.CV], Computer Vision and Pattern Recognition (cs.CV), [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Computer Science - Data Structures and Algorithms, Computer Science - Computer Vision and Pattern Recognition, [INFO.INFO-CV]Computer Science [cs]/Computer Vision and Pattern Recognition [cs.CV], Data Structures and Algorithms (cs.DS), [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS]
Abstract: Graph edit distance (GED) is a powerful and flexible graph matching paradigm that can be used to address different tasks in structural pattern recognition, machine learning, and data mining. In this paper, some new binary linear programming formulations for computing the exact GED between two graphs are proposed. A major strength of the formulations lies in their genericity since the GED can be computed between directed or undirected fully attributed graphs (i.e. with attributes on both vertices and edges). Moreover, a relaxation of the domain constraints in the formulations provides efficient lower bound approximations of the GED. A complete experimental study comparing the proposed formulations with 4 state-of-the-art algorithms for exact and approximate graph edit distances is provided. By considering both the quality of the proposed solution and the efficiency of the algorithms as performance criteria, the results show that none of the compared methods dominates the others in the Pareto sense. As a consequence, faced to a given real-world problem, a trade-off between quality and efficiency has to be chosen w.r.t. the application constraints. In this context, this paper provides a guide that can be used to choose the appropriate method.
Published: 2015

40. Dominated Colorings of Graphs

Author: Mohammed Haddad, Hamamache Kheddouci, Houcine Boumediene Merouane, Mustapha Chellali, Graphes, AlgOrithmes et AppLications (GOAL), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), 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)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Université Lumière - Lyon 2 (UL2), and Haddad, Mohammed
Subjects: Vertex (graph theory), [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Domination analysis, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], 01 natural sciences, Theoretical Computer Science, Combinatorics, Computer Science::Discrete Mathematics, 0202 electrical engineering, electronic engineering, information engineering, Discrete Mathematics and Combinatorics, Time complexity, Mathematics, Discrete mathematics, Complete coloring, 16. Peace & justice, Graph, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], 010201 computation theory & mathematics, Close relationship, 020201 artificial intelligence & image processing, [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC], Coloring problem
Abstract: In this paper, we introduce and study a new coloring problem of a graph called the dominated coloring. A dominated coloring of a graph $$G$$ G is a proper vertex coloring of $$G$$ G such that each color class is dominated by at least one vertex of $$G$$ G . The minimum number of colors among all dominated colorings is called the dominated chromatic number, denoted by $$\chi _{dom}(G)$$ ? d o m ( G ) . In this paper, we establish the close relationship between the dominated chromatic number $$\chi _{dom}(G)$$ ? d o m ( G ) and the total domination number $$\gamma _t(G)$$ ? t ( G ) ; and the equivalence for triangle-free graphs. We study the complexity of the problem by proving its NP-completeness for arbitrary graphs having $$\chi _{dom}(G) \ge 4$$ ? d o m ( G ) ? 4 and by giving a polynomial time algorithm for recognizing graphs having $$\chi _{dom}(G) \le 3$$ ? d o m ( G ) ≤ 3 . We also give some bounds for planar and star-free graphs and exact values for split graphs.
Published: 2015

41. Minimal Synchrony for Asynchronous Byzantine Consensus

Author: Bouzid, Zohir, Mostefaoui, Achour, Raynal, Michel, As Scalable As Possible: foundations of large scale dynamic distributed systems (ASAP), SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National de Recherche en Informatique et en Automatique (Inria)-École normale supérieure - Rennes (ENS Rennes)-Université de Bretagne Sud (UBS)-Centre National de la Recherche Scientifique (CNRS)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-CentraleSupélec-Télécom Bretagne-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria), Gestion de Données Distribuées [Nantes] (GDD), Laboratoire d'Informatique de Nantes Atlantique (LINA), Centre National de la Recherche Scientifique (CNRS)-Mines Nantes (Mines Nantes)-Université de Nantes (UN)-Centre National de la Recherche Scientifique (CNRS)-Mines Nantes (Mines Nantes)-Université de Nantes (UN), 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.), ANR-11-BS02-0014,DISPLEXITY,Calculabilité et complexité en distribué(2011), Raynal, Michel, BLANC - Calculabilité et complexité en distribué - - DISPLEXITY2011 - ANR-11-BS02-0014 - BLANC - VALID, Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), and Mines Nantes (Mines Nantes)-Université de Nantes (UN)-Centre National de la Recherche Scientifique (CNRS)-Mines Nantes (Mines Nantes)-Université de Nantes (UN)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Consensus, Lower bound, Byzantine process, Distributed algorithm, Reliable broadcast, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Optimal resilience, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO] Computer Science [cs], Asynchronous message-passing, Eventual timely channel, Adopt-commit, Signature-free algorithm, [INFO]Computer Science [cs], Feasibility condition
Abstract: Solving the consensus problem requires in one way or another that the underlying system satisfies some synchrony assumption. Considering an asynchronous message-passing system of n processes where (a) up to t < n/3 may commit Byzantine failures, and (b) each pair of processes is connected by two uni-directional channels (with possibly different timing properties), this paper investigates the synchrony assumption required to solve consensus, and presents a signature-free consensus algorithm whose synchrony requirement is the existence of a process that is an eventual t+1bisource. Such a process p is a correct process that eventually has (a) timely input channels from t correct processes and (b) timely output channels to t correct processes (these input and output channels can connect p to different subsets of processes). As this synchrony condition was shown to be necessary and sufficient in the stronger asynchronous system model (a) enriched with message authentication, and (b) where the channels are bidirectional and have the same timing properties in both directions, it follows that it is also necessary and sufficient in the weaker system model considered in the paper. In addition to the fact that it closes a long-lasting problem related to Byzantine agreement, a noteworthy feature of the proposed algorithm lies in its design simplicity, which is a first-class property.
Published: 2015

42. A PROPOSAL OF USING DEVS MODEL FOR PROCESS MINING

Author: Wang, Y., Gregory Zacharewicz, Chen, D., Traoré, M. K., Wang, Yan, Laboratoire de l'intégration, du matériau au système (IMS), Université Sciences et Technologies - Bordeaux 1 (UB)-Institut Polytechnique de Bordeaux-Centre National de la Recherche Scientifique (CNRS), Computational Geometry Lab, Carleton University, Institut Supérieur d'Informatique, de Modélisation et de leurs Applications (ISIMA), Université Blaise Pascal - Clermont-Ferrand 2 (UBP)-Ministère de l'Education nationale, de l’Enseignement supérieur et de la Recherche (M.E.N.E.S.R.), Université Blaise Pascal - Clermont-Ferrand 2 (UBP), Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes (LIMOS), Université Blaise Pascal - Clermont-Ferrand 2 (UBP)-Université d'Auvergne - Clermont-Ferrand I (UdA)-SIGMA Clermont (SIGMA Clermont)-Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS), Clermont Université, Laboratoire de l'intégration, du matériau au système ( IMS ), Université Sciences et Technologies - Bordeaux 1-Institut Polytechnique de Bordeaux-Centre National de la Recherche Scientifique ( CNRS ), Institut Supérieur d'Informatique, de Modélisation et de leurs Applications ( ISIMA ), Université Blaise Pascal - Clermont-Ferrand 2 ( UBP ) -Ministère de l'Éducation nationale, de l’Enseignement supérieur et de la Recherche ( M.E.N.E.S.R. ), Université Blaise Pascal - Clermont-Ferrand 2 ( UBP ), Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes ( LIMOS ), Centre National de la Recherche Scientifique ( CNRS ) -Sigma CLERMONT ( Sigma CLERMONT ) -Université d'Auvergne - Clermont-Ferrand I ( UdA ) -Université Blaise Pascal - Clermont-Ferrand 2 ( UBP ), Université Sciences et Technologies - Bordeaux 1-Institut Polytechnique de Bordeaux-Centre National de la Recherche Scientifique (CNRS), and SIGMA Clermont (SIGMA Clermont)-Université d'Auvergne - Clermont-Ferrand I (UdA)-Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Blaise Pascal - Clermont-Ferrand 2 (UBP)
Subjects: [ INFO.INFO-MO ] Computer Science [cs]/Modeling and Simulation, dynamic semantic, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], process mining, DEVS, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-MO] Computer Science [cs]/Modeling and Simulation, process discovery, [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation, [ INFO.INFO-DS ] Computer Science [cs]/Data Structures and Algorithms [cs.DS], time
Abstract: International audience; Process mining is a relative young research area which consists of process modeling and data mining. Process discovery as a part of the process mining focuses on converting event logs into process models. Petri Nets formalism is identified as the most convenient resulting process model. However, it is not entirely satisfying and needs to be improved with the purpose of covering the temporal aspects of the studied system. Compared with it, DEVS has the advantage of explicit and concurrent time and separating model from simulation. The objective of this paper is to specify DEVS model as the resulting process model. Based on the existing Two-Phased Approaches in process mining, a region-based approach with the suitable mapping is designed to convert the transition system directly to DEVS. A study case is presented to implement this approach. This paper is a position paper and it needs to be completed. In addition, a dynamic semantic should be designed to solve some typical representational limitations and a simulation engine should be selected. 1. INTRODUCTION Nowadays, the development of the information systems cannot be separated by the operational process. Moreover, more and more events with abundant process information are recorded. Despite the omnipresence of event data, most of the organizations analyze and build models based on expert assumption rather than quantified collected fact. Thanks to process mining [Van der Aalst, 2011], it provides the methods to discover monitor and improve actual processes by using event data to extract process-related information. Process mining combines process design by model-driven approaches and data mining. It includes three types: process discovery, process conformance and process enhancement. This paper anticipates and lays a cornerstone to make a breakthrough on the process discovery area. The purpose of discovery technique is to extract an event log with using recorded historical information and produce a model for simulation. In the process mining
Published: 2015

43. Using a Sparse Promoting Method in Linear Programming Approximations to Schedule Parallel Jobs

Author: Chrétien, Stéphane, Nicod, Jean-Marc, Philippe, Laurent, Sonigo, Veronika, Toch, Lamiel, Laboratoire de Mathématiques de Besançon (UMR 6623) (LMB), Centre National de la Recherche Scientifique (CNRS)-Université de Franche-Comté (UFC), Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC), Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174) (FEMTO-ST), Université de Technologie de Belfort-Montbeliard (UTBM)-Ecole Nationale Supérieure de Mécanique et des Microtechniques (ENSMM)-Centre National de la Recherche Scientifique (CNRS)-Université de Franche-Comté (UFC), Laboratoire de l'Informatique du Parallélisme (LIP), École normale supérieure de Lyon (ENS de Lyon)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Université de Bourgogne (UB)-Université de Franche-Comté (UFC), Université Bourgogne Franche-Comté [COMUE] (UBFC)-Université Bourgogne Franche-Comté [COMUE] (UBFC)-Centre National de la Recherche Scientifique (CNRS), Université de Technologie de Belfort-Montbeliard (UTBM)-Ecole Nationale Supérieure de Mécanique et des Microtechniques (ENSMM)-Université de Franche-Comté (UFC), Centre National de la Recherche Scientifique (CNRS)-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École normale supérieure - Lyon (ENS Lyon), and Femto-st, AS2M
Subjects: [INFO.INFO-SE] Computer Science [cs]/Software Engineering [cs.SE], [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-IU] Computer Science [cs]/Ubiquitous Computing, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-SE]Computer Science [cs]/Software Engineering [cs.SE], [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation, [SPI.AUTO]Engineering Sciences [physics]/Automatic, [INFO.INFO-IU]Computer Science [cs]/Ubiquitous Computing, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], [SPI.AUTO] Engineering Sciences [physics]/Automatic, [INFO.INFO-MA]Computer Science [cs]/Multiagent Systems [cs.MA], [INFO.INFO-ET] Computer Science [cs]/Emerging Technologies [cs.ET], [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], [INFO.INFO-ET]Computer Science [cs]/Emerging Technologies [cs.ET], [INFO.INFO-MA] Computer Science [cs]/Multiagent Systems [cs.MA], [INFO.INFO-MO] Computer Science [cs]/Modeling and Simulation, [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], [INFO.INFO-CR] Computer Science [cs]/Cryptography and Security [cs.CR]
Abstract: International audience; In this paper, we tackle the well‐known problem of scheduling a collection of parallel jobs on a set of processors either in a cluster or in a multiprocessor computer. For the makespan objective, that is, the completion time of the last job, this problem has been shown to be NP‐hard, and several heuristics have already been proposed to minimize the execution time. In this paper, we consider both rigid and moldable jobs. Our main contribution is the introduction of a new approach to the scheduling problem, based on the recent discoveries in the field of compressed sensing. In the proposed approach, all possible positions and shapes of the jobs are encoded into a matrix, and the scheduling is performed by selecting the best columns under natural constraints. Thus, the solution to the new scheduling formulation is naturally sparse, and we may use appropriate relaxations to achieve the optimization task in the quickest possible way. Among many possible relaxation strategies, we choose to minimize the
Published: 2015

44. OSLC-based Support for Integrated Development of Dependable Systems

Author: Iliasov, Alexei, Romanovsky, Alexander B., Laibinis, Linas, Troubitsynå, Elena, Busnel, Yann, Ilir Gashi, and Yann Busnel
Subjects: [INFO.INFO-DC] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-IT] Computer Science [cs]/Information Theory [cs.IT]
Abstract: Engineering of dependable systems is an inherently heterogenous field and involves the use of a wide range of techniques to analyse different aspects of the system behaviour and properties. Various standards typically prescribe a set of techniques to be used and a development process that should be followed to achieve a high degree of dependability and demonstrate it during certification. In this paper, we address the problem of building integrated environments that implement the processes required for engineering dependable systems. We discuss the use of OSLC (Open Services for Lifecycle Collaborations) – a rapidly developing industry-driven standard as a technological platform for such integration and present our ongoing work on building an integrated environment for formal development of dependable systems. Our prototype environment spans over requirements engineering, formal modelling and verification in Event-B as well as safety case construction. I. COMPLEMENTARITY AND DIVERSITY IN DEVELOPMENT PROCESS Development of dependable systems is an engineering field that is heavily regulated by standards [1]. Though standards are often criticised for their rigidness, they nevertheless capture the best practices and define recommendations based on decades of experience in engineering and operation of dependable systems. The majority of modern standards adopt process-oriented approaches to dependability assurance, i.e., they prescribe a set of methods and tools to be used to achieve dependability and demonstrate it during certification. Let us note that, despite differences in details, the majority of dependability-related standards focus on enforcing comple-mentarity and diversity in system development. Indeed, they aim at ensuring that there are not gaps in the analysis of the system behaviour in both nominal and off-nominal situations, failure analysis is complete, and several diverse layers of protection are built to break the chain of error propagation. Diversity and complementarity are enforced at both development process and system design levels. For instance, a development process typically complements fault avoidance with fault tolerance and fault removal; diversity is also employed in designing software and hardware to mitigate a risk of common cause failures. To follow the recommendations prescribed by standards and ensure that diversity and complementarity are properly implemented, the developers should be able to build integrated engineering environments that establish a correct and efficient flow of information within the development process. The development process generates a large amount of heterogeneous information – requirements, models, designs, tests, documentations, safety cases, etc. Obviously, to efficiently handle it, we need to provide the engineers with an automated support that establishes common information space, supports an efficient dynamic information flow and enables seamless integration of diverse tools. In this paper, we argue that OSLC provides us with a suitable technology to achieve these goals. Next we give a brief overview of OSLC.
Published: 2015

45. A KLEENE THEOREM FOR LANGUAGES OF WORDS INDEXED BY LINEAR ORDERINGS

Author: Olivier Carton, Alexis Bès, Carton, Olivier, Laboratoire d'Algorithmique Complexité et Logique (LACL), Université Paris-Est Créteil Val-de-Marne - Paris 12 (UPEC UP12)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), and Bès, Alexis
Subjects: Discrete mathematics, 010102 general mathematics, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Kleene theorem, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing), 0102 computer and information sciences, 02 engineering and technology, Linear ordering, 01 natural sciences, Automaton, Philosophy of language, Kleene algebra, Combinatorics, Indexed language, 010201 computation theory & mathematics, 0202 electrical engineering, electronic engineering, information engineering, Computer Science (miscellaneous), Countable set, 020201 artificial intelligence & image processing, 0101 mathematics, Computer Science::Formal Languages and Automata Theory, Mathematics
Abstract: In a preceding paper, Bruyère and Carton introduced automata, as well as rational expressions, which allow to deal with words indexed by linear orderings. A Kleene-like theorem was proved for words indexed by countable scattered linear orderings. In this paper we extend this result to languages of words indexed by all linear orderings.
Published: 2006

46. TransModE: Translational Knowledge Graph Embedding Using Modular Arithmetic

Author: Baalbaki, Hussein, Hazimeh, Hussein, Harb, Hassan, Angarita, Rafael, and Angarita, Rafael
Subjects: Reasoning, Knowledge Graph Embedding, General Earth and Planetary Sciences, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Knowledge Graphs, Link Prediction, General Environmental Science
Abstract: In order to improve link prediction process in a knowledge graph, we tackle the problem of learning representations of entities and relations. The strength of the existing models in this domain mainly relies on its ability of modeling and inferring the patterns of the relations. In this paper, we propose a new knowledge graph embedding approach called TransModE that has the ability to represent all simple and complex relation patterns. Inspired by TransE, TransModE represents the relations between the entities of a knowledge graph as a transition in the modulus space. Experimenting our model on multiple benchmark knowledge graphs shows the simplicity and the scalability of TransModE. It also shows that TransModE outperforms existing state-of-the-art models by being able to infer and model all types of relations.
Published: 2022

47. Determinization of transducers over finite and infinite words

Author: Marie-Pierre Béal, Olivier Carton, Laboratoire d'Informatique Gaspard-Monge (LIGM), Université Paris-Est Marne-la-Vallée (UPEM)-École des Ponts ParisTech (ENPC)-ESIEE Paris-Fédération de Recherche Bézout-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-Fédération de Recherche Bézout-ESIEE Paris-École des Ponts ParisTech (ENPC)-Université Paris-Est Marne-la-Vallée (UPEM), and Béal, Marie-Pierre
Subjects: Subsequential limit, Determinization, General Computer Science, Transducers, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Infinite words, 0102 computer and information sciences, 02 engineering and technology, Characterization (mathematics), 01 natural sciences, Automata, Theoretical Computer Science, 0202 electrical engineering, electronic engineering, information engineering, ComputingMilieux_MISCELLANEOUS, Mathematics, Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing), State (functional analysis), 16. Peace & justice, Automaton, Algebra, Transducer, 010201 computation theory & mathematics, 020201 artificial intelligence & image processing, Algorithm, Computer Science::Formal Languages and Automata Theory, Computer Science(all)
Abstract: We study the determinization of transducers over finite and infinite words. The first part of the paper is devoted to finite words. We recall the characterization of subsequential functions due to Choffrut. We describe here a known algorithm to determinize a transducer.In the case of infinite words, we consider transducers with all their states final. We give an effective characterization of sequential functions over infinite words. We describe an algorithm to determinize transducers over infinite words. This part contains the main novel results of the paper.
Published: 2002

48. Personalized Product Design Through Digital Fabrication

Author: A. (Sander) L. M. Minnoye, Farzam Tajdari, E. (Zjenja) L. Doubrovski, Jun Wu, Felix Kwa, Willemijn S. Elkhuizen, Toon Huysmans, Yu (Wolf) Song, and Tajdari, Farzam
Subjects: human modelling. computational design, product evaluation, Personalized product design, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 3D scanning, additive manufacturing
Abstract: Personalized designs bring added value to the products and the users. Meanwhile, they also pose challenges to the product design process as each product differs. In this paper, with the focus on personalized fit, we present an overview as well as details of the personalized design process based on design practice. The general workflow of personalized product design is introduced first. Then different steps in the workflow such as human data/parameters acquisition, computational design, design for digital fabrication, and product evaluation are presented. Tools and methods that are often used in different steps in the process are also outlined where in human data acquisition, 3D scanning, and digital human models are addressed. For computational design, the use of computational thinking tools such as abstraction, decomposition, pattern recognition and algorithms are discussed. In design for digital fabrication, additive manufacturing methods (e.g. FDM), and their requirements on the design are highlighted. For product evaluation, both functional evaluation and usability evaluation are considered and the evaluation results can be the starting point of the next design iteration. Finally, several case studies are presented for a better understanding of the workflow, the importance of different steps in the workflow and the deviations in the approach regarding different contexts. In conclusion, we intend to provide designers a holistic view of the design process in designing personalized products as well as help practitioners trigger innovations regarding each step of the process.
Published: 2022

49. Linear Temporal Logic for Regular Cost Functions

Author: Denis Kuperberg, Technische Universität Munchen - Université Technique de Munich [Munich, Allemagne] (TUM), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), and Dürr, Christoph
Subjects: FOS: Computer and information sciences, [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Computer Science - Logic in Computer Science, General Computer Science, Formal Languages and Automata Theory (cs.FL), Computer science, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Computer Science - Formal Languages and Automata Theory, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Expressive power, Theoretical Computer Science, Regular language, Linear temporal logic, [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL], Computer Science::Logic in Computer Science, 0202 electrical engineering, electronic engineering, information engineering, Equivalence (formal languages), 000 Computer science, knowledge, general works, Decision problem, Logic in Computer Science (cs.LO), Automaton, Decidability, Algebra, TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES, 010201 computation theory & mathematics, Computer Science, [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC], 020201 artificial intelligence & image processing
Abstract: Regular cost functions have been introduced recently as an extension to the notion of regular languages with counting capabilities, which retains strong closure, equivalence, and decidability properties. The specificity of cost functions is that exact values are not considered, but only estimated. In this paper, we define an extension of Linear Temporal Logic (LTL) over finite words to describe cost functions. We give an explicit translation from this new logic to two dual form of cost automata, and we show that the natural decision problems for this logic are PSPACE-complete, as it is the case in the classical setting. We then algebraically characterize the expressive power of this logic, using a new syntactic congruence for cost functions introduced in this paper., 37 pages, 13 figures, accepted to LMCS, updated version 08/02/2017
Published: 2014

50. The determinacy of context-free games

Author: Olivier Finkel, Dürr, Christoph, Christoph Dürr, Thomas Wilke, Équipe de Logique Mathématique (ELM), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS), Christoph Dürr and Thomas Wilke, Institut de Mathématiques de Jussieu (IMJ), and Université Pierre et Marie Curie - Paris 6 (UPMC)-Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS)
Subjects: FOS: Computer and information sciences, Determinacy, Computer Science - Logic in Computer Science, Mathematics::General Topology, [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], 01 natural sciences, models of set theory, independence from the axiomatic system ZFC, Computer Science - Computer Science and Game Theory, context-free games, Computer Science::Logic in Computer Science, Gale-Stewart games, logic in computer science, Axiom of projective determinacy, Set theory, GeneralLiterature_REFERENCE(e.g.,dictionaries,encyclopedias,glossaries), Mathematics, [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT], 1-counter automaton, [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO], 16. Peace & justice, Wadge hierarchy, Wadge games, Mathematics::Logic, 010201 computation theory & mathematics, ComputingMethodologies_DOCUMENTANDTEXTPROCESSING, [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC], Logic (math.LO), Computer Science and Game Theory (cs.GT), [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], Computer Science::Computer Science and Game Theory, Logic, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Büchi automaton, Context (language use), 0102 computer and information sciences, ACM 1998 classifications: F.1.1 Models of Computation, F.4.1 Mathematical Logic, effective analytic determinacy, Large cardinal, FOS: Mathematics, Automata and formal languages, 0101 mathematics, Discrete mathematics, 010102 general mathematics, Mathematics - Logic, Logic in Computer Science (cs.LO), Philosophy, [MATH.MATH-LO]Mathematics [math]/Logic [math.LO], determinacy, Descriptive set theory
Abstract: We prove that the determinacy of Gale-Stewart games whose winning sets are accepted by real-time 1-counter B\"uchi automata is equivalent to the determinacy of (effective) analytic Gale-Stewart games which is known to be a large cardinal assumption. We show also that the determinacy of Wadge games between two players in charge of omega-languages accepted by 1-counter B\"uchi automata is equivalent to the (effective) analytic Wadge determinacy. Using some results of set theory we prove that one can effectively construct a 1-counter B\"uchi automaton A and a B\"uchi automaton B such that: (1) There exists a model of ZFC in which Player 2 has a winning strategy in the Wadge game W(L(A), L(B)); (2) There exists a model of ZFC in which the Wadge game W(L(A), L(B)) is not determined. Moreover these are the only two possibilities, i.e. there are no models of ZFC in which Player 1 has a winning strategy in the Wadge game W(L(A), L(B))., Comment: This paper is an extended version of a STACS 2012 conference paper [arXiv:1112.1186]. It will appear in the Journal of Symbolic Logic
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

726 results

Search Results

Select search scope, currently: Articles

Catalog

books, media & more in Jio Institute collections

Articles

journal articles & other e-resources