-
BiPer: Binary Neural Networks using a Periodic Function
Authors:
Edwin Vargas,
Claudia Correa,
Carlos Hinojosa,
Henry Arguello
Abstract:
Quantized neural networks employ reduced precision representations for both weights and activations. This quantization process significantly reduces the memory requirements and computational complexity of the network. Binary Neural Networks (BNNs) are the extreme quantization case, representing values with just one bit. Since the sign function is typically used to map real values to binary values,…
▽ More
Quantized neural networks employ reduced precision representations for both weights and activations. This quantization process significantly reduces the memory requirements and computational complexity of the network. Binary Neural Networks (BNNs) are the extreme quantization case, representing values with just one bit. Since the sign function is typically used to map real values to binary values, smooth approximations are introduced to mimic the gradients during error backpropagation. Thus, the mismatch between the forward and backward models corrupts the direction of the gradient, causing training inconsistency problems and performance degradation. In contrast to current BNN approaches, we propose to employ a binary periodic (BiPer) function during binarization. Specifically, we use a square wave for the forward pass to obtain the binary values and employ the trigonometric sine function with the same period of the square wave as a differentiable surrogate during the backward pass. We demonstrate that this approach can control the quantization error by using the frequency of the periodic function and improves network performance. Extensive experiments validate the effectiveness of BiPer in benchmark datasets and network architectures, with improvements of up to 1% and 0.69% with respect to state-of-the-art methods in the classification task over CIFAR-10 and ImageNet, respectively. Our code is publicly available at https://github.com/edmav4/BiPer.
△ Less
Submitted 1 April, 2024;
originally announced April 2024.
-
Program-Based Strategy Induction for Reinforcement Learning
Authors:
Carlos G. Correa,
Thomas L. Griffiths,
Nathaniel D. Daw
Abstract:
Typical models of learning assume incremental estimation of continuously-varying decision variables like expected rewards. However, this class of models fails to capture more idiosyncratic, discrete heuristics and strategies that people and animals appear to exhibit. Despite recent advances in strategy discovery using tools like recurrent networks that generalize the classic models, the resulting…
▽ More
Typical models of learning assume incremental estimation of continuously-varying decision variables like expected rewards. However, this class of models fails to capture more idiosyncratic, discrete heuristics and strategies that people and animals appear to exhibit. Despite recent advances in strategy discovery using tools like recurrent networks that generalize the classic models, the resulting strategies are often onerous to interpret, making connections to cognition difficult to establish. We use Bayesian program induction to discover strategies implemented by programs, letting the simplicity of strategies trade off against their effectiveness. Focusing on bandit tasks, we find strategies that are difficult or unexpected with classical incremental learning, like asymmetric learning from rewarded and unrewarded trials, adaptive horizon-dependent random exploration, and discrete state switching.
△ Less
Submitted 26 February, 2024;
originally announced February 2024.
-
Exploring the hierarchical structure of human plans via program generation
Authors:
Carlos G. Correa,
Sophia Sanborn,
Mark K. Ho,
Frederick Callaway,
Nathaniel D. Daw,
Thomas L. Griffiths
Abstract:
Human behavior is inherently hierarchical, resulting from the decomposition of a task into subtasks or an abstract action into concrete actions. However, behavior is typically measured as a sequence of actions, which makes it difficult to infer its hierarchical structure. In this paper, we explore how people form hierarchically-structured plans, using an experimental paradigm that makes hierarchic…
▽ More
Human behavior is inherently hierarchical, resulting from the decomposition of a task into subtasks or an abstract action into concrete actions. However, behavior is typically measured as a sequence of actions, which makes it difficult to infer its hierarchical structure. In this paper, we explore how people form hierarchically-structured plans, using an experimental paradigm that makes hierarchical representations observable: participants create programs that produce sequences of actions in a language with explicit hierarchical structure. This task lets us test two well-established principles of human behavior: utility maximization (i.e. using fewer actions) and minimum description length (MDL; i.e. having a shorter program). We find that humans are sensitive to both metrics, but that both accounts fail to predict a qualitative feature of human-created programs, namely that people prefer programs with reuse over and above the predictions of MDL. We formalize this preference for reuse by extending the MDL account into a generative model over programs, modeling hierarchy choice as the induction of a grammar over actions. Our account can explain the preference for reuse and provides the best prediction of human behavior, going beyond simple accounts of compressibility to highlight a principle that guides hierarchical planning.
△ Less
Submitted 30 November, 2023;
originally announced November 2023.
-
Structurally guided task decomposition in spatial navigation tasks
Authors:
Ruiqi He,
Carlos G. Correa,
Thomas L. Griffiths,
Mark K. Ho
Abstract:
How are people able to plan so efficiently despite limited cognitive resources? We aimed to answer this question by extending an existing model of human task decomposition that can explain a wide range of simple planning problems by adding structure information to the task to facilitate planning in more complex tasks. The extended model was then applied to a more complex planning domain of spatial…
▽ More
How are people able to plan so efficiently despite limited cognitive resources? We aimed to answer this question by extending an existing model of human task decomposition that can explain a wide range of simple planning problems by adding structure information to the task to facilitate planning in more complex tasks. The extended model was then applied to a more complex planning domain of spatial navigation. Our results suggest that our framework can correctly predict the navigation strategies of the majority of the participants in an online experiment.
△ Less
Submitted 3 October, 2023;
originally announced October 2023.
-
SWIFT: A modern highly-parallel gravity and smoothed particle hydrodynamics solver for astrophysical and cosmological applications
Authors:
Matthieu Schaller,
Josh Borrow,
Peter W. Draper,
Mladen Ivkovic,
Stuart McAlpine,
Bert Vandenbroucke,
Yannick Bahé,
Evgenii Chaikin,
Aidan B. G. Chalk,
Tsang Keung Chan,
Camila Correa,
Marcel van Daalen,
Willem Elbers,
Pedro Gonnet,
Loïc Hausammann,
John Helly,
Filip Huško,
Jacob A. Kegerreis,
Folkert S. J. Nobels,
Sylvia Ploeckinger,
Yves Revaz,
William J. Roper,
Sergio Ruiz-Bonilla,
Thomas D. Sandnes,
Yolan Uyttenhove
, et al. (2 additional authors not shown)
Abstract:
Numerical simulations have become one of the key tools used by theorists in all the fields of astrophysics and cosmology. The development of modern tools that target the largest existing computing systems and exploit state-of-the-art numerical methods and algorithms is thus crucial. In this paper, we introduce the fully open-source highly-parallel, versatile, and modular coupled hydrodynamics, gra…
▽ More
Numerical simulations have become one of the key tools used by theorists in all the fields of astrophysics and cosmology. The development of modern tools that target the largest existing computing systems and exploit state-of-the-art numerical methods and algorithms is thus crucial. In this paper, we introduce the fully open-source highly-parallel, versatile, and modular coupled hydrodynamics, gravity, cosmology, and galaxy-formation code SWIFT. The software package exploits hybrid shared- and distributed-memory task-based parallelism, asynchronous communications, and domain-decomposition algorithms based on balancing the workload, rather than the data, to efficiently exploit modern high-performance computing cluster architectures. Gravity is solved for using a fast-multipole-method, optionally coupled to a particle mesh solver in Fourier space to handle periodic volumes. For gas evolution, multiple modern flavours of Smoothed Particle Hydrodynamics are implemented. SWIFT also evolves neutrinos using a state-of-the-art particle-based method. Two complementary networks of sub-grid models for galaxy formation as well as extensions to simulate planetary physics are also released as part of the code. An extensive set of output options, including snapshots, light-cones, power spectra, and a coupling to structure finders are also included. We describe the overall code architecture, summarise the consistency and accuracy tests that were performed, and demonstrate the excellent weak-scaling performance of the code using a representative cosmological hydrodynamical problem with $\approx$$300$ billion particles. The code is released to the community alongside extensive documentation for both users and developers, a large selection of example test problems, and a suite of tools to aid in the analysis of large simulations run with SWIFT.
△ Less
Submitted 29 March, 2024; v1 submitted 22 May, 2023;
originally announced May 2023.
-
Soft Skills Centrality in Graduate Studies Offerings
Authors:
María del Pilar García-Chitiva,
Juan C. Correa
Abstract:
Is it possible to measure how critical soft skills like leadership or teamwork are from the viewpoint of graduate studies offerings? This paper provides a conceptual and methodological framework that introduces the concept of a bipartite network as a practical way to estimate the importance of soft skills as socio-emotional abilities trained in graduate studies. We examined 230 graduate programs o…
▽ More
Is it possible to measure how critical soft skills like leadership or teamwork are from the viewpoint of graduate studies offerings? This paper provides a conceptual and methodological framework that introduces the concept of a bipartite network as a practical way to estimate the importance of soft skills as socio-emotional abilities trained in graduate studies. We examined 230 graduate programs offered by 49 higher education institutions in Colombia to estimate the empirical importance of soft skills from the viewpoint of graduate studies offerings. The results show that: a) graduate programs in Colombia share 31 soft skills in their intended learning outcomes; b) the centrality of these skills varies as a function of the graduate program, although this variation was not statistically significant; and c) while most central soft skills tend to be those related to creativity (i.e., creation or generation of ideas or projects), leadership (to lead or teamwork), and analytical orientation (e.g., evaluating situations and solving problems), less central were those related to empathy (i.e., understanding others and acknowledgment of others), ethical thinking, and critical thinking, posing the question if too much emphasis on most visible skills might imply an unbalance in the opportunities to enhancing other soft skills such as ethical thinking.
△ Less
Submitted 27 July, 2023; v1 submitted 23 March, 2023;
originally announced March 2023.
-
Humans decompose tasks by trading off utility and computational cost
Authors:
Carlos G. Correa,
Mark K. Ho,
Frederick Callaway,
Nathaniel D. Daw,
Thomas L. Griffiths
Abstract:
Human behavior emerges from planning over elaborate decompositions of tasks into goals, subgoals, and low-level actions. How are these decompositions created and used? Here, we propose and evaluate a normative framework for task decomposition based on the simple idea that people decompose tasks to reduce the overall cost of planning while maintaining task performance. Analyzing 11,117 distinct gra…
▽ More
Human behavior emerges from planning over elaborate decompositions of tasks into goals, subgoals, and low-level actions. How are these decompositions created and used? Here, we propose and evaluate a normative framework for task decomposition based on the simple idea that people decompose tasks to reduce the overall cost of planning while maintaining task performance. Analyzing 11,117 distinct graph-structured planning tasks, we find that our framework justifies several existing heuristics for task decomposition and makes predictions that can be distinguished from two alternative normative accounts. We report a behavioral study of task decomposition ($N=806$) that uses 30 randomly sampled graphs, a larger and more diverse set than that of any previous behavioral study on this topic. We find that human responses are more consistent with our framework for task decomposition than alternative normative accounts and are most consistent with a heuristic -- betweenness centrality -- that is justified by our approach. Taken together, our results provide new theoretical insight into the computational principles underlying the intelligent structuring of goal-directed behavior.
△ Less
Submitted 7 November, 2022;
originally announced November 2022.
-
Using Natural Language and Program Abstractions to Instill Human Inductive Biases in Machines
Authors:
Sreejan Kumar,
Carlos G. Correa,
Ishita Dasgupta,
Raja Marjieh,
Michael Y. Hu,
Robert D. Hawkins,
Nathaniel D. Daw,
Jonathan D. Cohen,
Karthik Narasimhan,
Thomas L. Griffiths
Abstract:
Strong inductive biases give humans the ability to quickly learn to perform a variety of tasks. Although meta-learning is a method to endow neural networks with useful inductive biases, agents trained by meta-learning may sometimes acquire very different strategies from humans. We show that co-training these agents on predicting representations from natural language task descriptions and programs…
▽ More
Strong inductive biases give humans the ability to quickly learn to perform a variety of tasks. Although meta-learning is a method to endow neural networks with useful inductive biases, agents trained by meta-learning may sometimes acquire very different strategies from humans. We show that co-training these agents on predicting representations from natural language task descriptions and programs induced to generate such tasks guides them toward more human-like inductive biases. Human-generated language descriptions and program induction models that add new learned primitives both contain abstract concepts that can compress description length. Co-training on these representations result in more human-like behavior in downstream meta-reinforcement learning agents than less abstract controls (synthetic language descriptions, program induction without learned primitives), suggesting that the abstraction supported by these representations is key.
△ Less
Submitted 5 February, 2023; v1 submitted 23 May, 2022;
originally announced May 2022.
-
People construct simplified mental representations to plan
Authors:
Mark K. Ho,
David Abel,
Carlos G. Correa,
Michael L. Littman,
Jonathan D. Cohen,
Thomas L. Griffiths
Abstract:
One of the most striking features of human cognition is the capacity to plan. Two aspects of human planning stand out: its efficiency and flexibility. Efficiency is especially impressive because plans must often be made in complex environments, and yet people successfully plan solutions to myriad everyday problems despite having limited cognitive resources. Standard accounts in psychology, economi…
▽ More
One of the most striking features of human cognition is the capacity to plan. Two aspects of human planning stand out: its efficiency and flexibility. Efficiency is especially impressive because plans must often be made in complex environments, and yet people successfully plan solutions to myriad everyday problems despite having limited cognitive resources. Standard accounts in psychology, economics, and artificial intelligence have suggested human planning succeeds because people have a complete representation of a task and then use heuristics to plan future actions in that representation. However, this approach generally assumes that task representations are fixed. Here, we propose that task representations can be controlled and that such control provides opportunities to quickly simplify problems and more easily reason about them. We propose a computational account of this simplification process and, in a series of pre-registered behavioral experiments, show that it is subject to online cognitive control and that people optimally balance the complexity of a task representation and its utility for planning and acting. These results demonstrate how strategically perceiving and conceiving problems facilitates the effective use of limited cognitive resources.
△ Less
Submitted 26 November, 2022; v1 submitted 14 May, 2021;
originally announced May 2021.
-
Resource-rational Task Decomposition to Minimize Planning Costs
Authors:
Carlos G. Correa,
Mark K. Ho,
Fred Callaway,
Thomas L. Griffiths
Abstract:
People often plan hierarchically. That is, rather than planning over a monolithic representation of a task, they decompose the task into simpler subtasks and then plan to accomplish those. Although much work explores how people decompose tasks, there is less analysis of why people decompose tasks in the way they do. Here, we address this question by formalizing task decomposition as a resource-rat…
▽ More
People often plan hierarchically. That is, rather than planning over a monolithic representation of a task, they decompose the task into simpler subtasks and then plan to accomplish those. Although much work explores how people decompose tasks, there is less analysis of why people decompose tasks in the way they do. Here, we address this question by formalizing task decomposition as a resource-rational representation problem. Specifically, we propose that people decompose tasks in a manner that facilitates efficient use of limited cognitive resources given the structure of the environment and their own planning algorithms. Using this model, we replicate several existing findings. Our account provides a normative explanation for how people identify subtasks as well as a framework for studying how people reason, plan, and act using resource-rational representations.
△ Less
Submitted 27 July, 2020;
originally announced July 2020.
-
The Sci-hub Effect: Sci-hub downloads lead to more article citations
Authors:
J. C. Correa,
H. Laverde-Rojas,
F. Marmolejo-Ramos,
J. Tejada,
Š. Bahník
Abstract:
Citations are often used as a metric of the impact of scientific publications. Here, we examine how the number of downloads from Sci-hub as well as various characteristics of publications and their authors predicts future citations. Using data from 12 leading journals in economics, consumer research, neuroscience, and multidisciplinary research, we found that articles downloaded from Sci-hub were…
▽ More
Citations are often used as a metric of the impact of scientific publications. Here, we examine how the number of downloads from Sci-hub as well as various characteristics of publications and their authors predicts future citations. Using data from 12 leading journals in economics, consumer research, neuroscience, and multidisciplinary research, we found that articles downloaded from Sci-hub were cited 1.72 times more than papers not downloaded from Sci-hub and that the number of downloads from Sci-hub was a robust predictor of future citations. Among other characteristics of publications, the number of figures in a manuscript consistently predicts its future citations. The results suggest that limited access to publications may limit some scientific research from achieving its full impact.
△ Less
Submitted 29 June, 2020; v1 submitted 26 June, 2020;
originally announced June 2020.
-
The Consistency of Trust-Sales Relationship in Latin-American E-commerce
Authors:
Juan C. Correa,
Henry Laverde-Rojas,
Camilo A. Martinez,
Oscar Javier Camargo,
Gustavo Rojas-Matute,
Marithza Sandoval-Escobar
Abstract:
Customer's trust in vendors' reputation is a key factor that facilitates economic transactions in e-commerce platforms. Although the trust-sales relationship is assumed robust and consistent, its empirical evidence remains neglected for Latin American countries. This work aims to provide a data-driven comprehensive framework for extracting valuable knowledge from public data available in the leadi…
▽ More
Customer's trust in vendors' reputation is a key factor that facilitates economic transactions in e-commerce platforms. Although the trust-sales relationship is assumed robust and consistent, its empirical evidence remains neglected for Latin American countries. This work aims to provide a data-driven comprehensive framework for extracting valuable knowledge from public data available in the leading Latin American e-commerce platform with commercial operations in 18 countries. Only Argentina, Brasil, Chile, Colombia, Ecuador, Mexico, Uruguay, and Venezuela showed the highest trust indexes among all nations analyzed. The trust-sales relationship was statistically inconsistent across nations but worked as the most important predictor of sales, followed by purchase intention and price.
△ Less
Submitted 11 September, 2021; v1 submitted 1 November, 2019;
originally announced November 2019.
-
On the combinatorics of the 2-class classification problem
Authors:
Ricardo C. Corrêa,
Diego Delle Donne,
Javier Marenco
Abstract:
A set of points $X = X_B \cup X_R \subseteq \mathbb{R}^d$ is linearly separable if the convex hulls of $X_B$ and $X_R$ are disjoint, hence there exists a hyperplane separating $X_B$ from $X_R$. Such a hyperplane provides a method for classifying new points, according to which side of the hyperplane the new points lie. When such a linear separation is not possible, it may still be possible to parti…
▽ More
A set of points $X = X_B \cup X_R \subseteq \mathbb{R}^d$ is linearly separable if the convex hulls of $X_B$ and $X_R$ are disjoint, hence there exists a hyperplane separating $X_B$ from $X_R$. Such a hyperplane provides a method for classifying new points, according to which side of the hyperplane the new points lie. When such a linear separation is not possible, it may still be possible to partition $X_B$ and $X_R$ into prespecified numbers of groups, in such a way that every group from $X_B$ is linearly separable from every group from $X_R$. We may also discard some points as outliers, and seek to minimize the number of outliers necessary to find such a partition. Based on these ideas, Bertsimas and Shioda proposed the classification and regression by integer optimization (CRIO) method in 2007. In this work we explore the integer programming aspects of the classification part of CRIO, in particular theoretical properties of the associated formulation. We are able to find facet-inducing inequalities coming from the stable set polytope, hence showing that this classification problem has exploitable combinatorial properties.
△ Less
Submitted 28 December, 2017; v1 submitted 19 June, 2017;
originally announced June 2017.
-
Ideological Consumerism in Colombian Elections, 2015: Links between Political Ideology, Twitter Activity and Electoral Results
Authors:
Juan C. Correa,
Jorge Camargo
Abstract:
Propagation of political ideologies in social networks has shown a notorious impact on voting behavior. Both the contents of the messages (the ideology) and the politicians' influence on their online audiences (their followers) have been associated with such an impact. Here we evaluate which of these factors exerted a major role in deciding electoral results of the 2015 Colombian regional election…
▽ More
Propagation of political ideologies in social networks has shown a notorious impact on voting behavior. Both the contents of the messages (the ideology) and the politicians' influence on their online audiences (their followers) have been associated with such an impact. Here we evaluate which of these factors exerted a major role in deciding electoral results of the 2015 Colombian regional elections by evaluating the linguistic similarity of political ideologies and their influence on the Twitter sphere. The electoral results proved to be strongly associated with tweets and retweets and not with the linguistic content of their ideologies or their Twitter followers. Suggestions on new ways to analyze electoral processes are finally discussed.
△ Less
Submitted 5 August, 2016; v1 submitted 4 August, 2016;
originally announced August 2016.
-
General Cut-Generating Procedures for the Stable Set Polytope
Authors:
Ricardo C. Corrêa,
Diego Delle Donne,
Ivo Koch,
Javier Marenco
Abstract:
We propose general separation procedures for generating cuts for the stable set polytope, inspired by a procedure by Rossi and Smriglio and applying a lifting method by Xavier and Campêlo. In contrast to existing cut-generating procedures, ours generate both rank and non-rank valid inequalities, hence they are of a more general nature than existing methods. This is accomplished by iteratively solv…
▽ More
We propose general separation procedures for generating cuts for the stable set polytope, inspired by a procedure by Rossi and Smriglio and applying a lifting method by Xavier and Campêlo. In contrast to existing cut-generating procedures, ours generate both rank and non-rank valid inequalities, hence they are of a more general nature than existing methods. This is accomplished by iteratively solving a lifting problem, which consists of a maximum weighted stable set problem on a smaller graph. Computational experience on DIMACS benchmark instances shows that the proposed approach may be a useful tool for generating cuts for the stable set polytope.
△ Less
Submitted 28 December, 2017; v1 submitted 29 December, 2015;
originally announced December 2015.
-
Polyhedral studies of vertex coloring problems: The asymmetric representatives formulation
Authors:
Victor Campos,
Ricardo C. Corrêa,
Diego Delle Donne,
Javier Marenco,
Annegret Wagler
Abstract:
Despite the fact that some vertex coloring problems are polynomially solvable on certain graph classes, most of these problems are not "under control" from a polyhedral point of view. The equivalence between \emph{optimization} and \emph{polyhedral separation} suggests that, for these problems, there must exist formulations admitting some elegant characterization for the polytopes associated to th…
▽ More
Despite the fact that some vertex coloring problems are polynomially solvable on certain graph classes, most of these problems are not "under control" from a polyhedral point of view. The equivalence between \emph{optimization} and \emph{polyhedral separation} suggests that, for these problems, there must exist formulations admitting some elegant characterization for the polytopes associated to them. Therefore, it is interesting to study known formulations for vertex coloring with the goal of finding such characterizations. In this work we study the asymmetric representatives formulation and we show that the corresponding coloring polytope, for a given graph $G$, can be interpreted as the stable set polytope of another graph obtained from $G$. This result allows us to derive complete characterizations for the corresponding coloring polytope for some families of graphs, based on known complete characterizations for the stable set polytope.
△ Less
Submitted 28 August, 2015;
originally announced September 2015.
-
Musical elements in the discrete-time representation of sound
Authors:
Renato Fabbri,
Vilson Vieira da Silva Junior,
Antônio Carlos Silvano Pessotti,
Débora Cristina Corrêa,
Osvaldo N. Oliveira Jr
Abstract:
The representation of basic elements of music in terms of discrete audio signals is often used in software for musical creation and design. Nevertheless, there is no unified approach that relates these elements to the discrete samples of digitized sound. In this article, each musical element is related by equations and algorithms to the discrete-time samples of sounds, and each of these relations…
▽ More
The representation of basic elements of music in terms of discrete audio signals is often used in software for musical creation and design. Nevertheless, there is no unified approach that relates these elements to the discrete samples of digitized sound. In this article, each musical element is related by equations and algorithms to the discrete-time samples of sounds, and each of these relations are implemented in scripts within a software toolbox, referred to as MASS (Music and Audio in Sample Sequences). The fundamental element, the musical note with duration, volume, pitch and timbre, is related quantitatively to characteristics of the digital signal. Internal variations of a note, such as tremolos, vibratos and spectral fluctuations, are also considered, which enables the synthesis of notes inspired by real instruments and new sonorities. With this representation of notes, resources are provided for the generation of higher scale musical structures, such as rhythmic meter, pitch intervals and cycles. This framework enables precise and trustful scientific experiments, data sonification and is useful for education and art. The efficacy of MASS is confirmed by the synthesis of small musical pieces using basic notes, elaborated notes and notes in music, which reflects the organization of the toolbox and thus of this article. It is possible to synthesize whole albums through collage of the scripts and settings specified by the user. With the open source paradigm, the toolbox can be promptly scrutinized, expanded in co-authorship processes and used with freedom by musicians, engineers and other interested parties. In fact, MASS has already been employed for diverse purposes which include music production, artistic presentations, psychoacoustic experiments and computer language diffusion where the appeal of audiovisual artifacts is exploited for education.
△ Less
Submitted 26 October, 2017; v1 submitted 21 December, 2014;
originally announced December 2014.
-
A Bit-Parallel Russian Dolls Search for a Maximum Cardinality Clique in a Graph
Authors:
Ricardo C. Corrêa,
Philippe Michelon,
Bertrand Le Cun,
Thierry Mautor,
Diego Delle Donne
Abstract:
Finding the clique of maximum cardinality in an arbitrary graph is an NP-Hard problem that has many applications, which has motivated studies to solve it exactly despite its difficulty. The great majority of algorithms proposed in the literature are based on the Branch and Bound method. In this paper, we propose an exact algorithm for the maximum clique problem based on the Russian Dolls Search me…
▽ More
Finding the clique of maximum cardinality in an arbitrary graph is an NP-Hard problem that has many applications, which has motivated studies to solve it exactly despite its difficulty. The great majority of algorithms proposed in the literature are based on the Branch and Bound method. In this paper, we propose an exact algorithm for the maximum clique problem based on the Russian Dolls Search method. When compared to Branch and Bound, the main difference of the Russian Dolls method is that the nodes of its search tree correspond to decision subproblems, instead of the optimization subproblems of the Branch and Bound method. In comparison to a first implementation of this Russian Dolls method from the literature, several improvements are presented. Some of them are adaptations of techniques already employed successfully in Branch and Bound algorithms, like the use of approximate coloring for pruning purposes and bit-parallel operations. Two different coloring heuristics are tested: the standard greedy and the greedy with recoloring. Other improvements are directly related to the Russian Dolls scheme: the adoption of recursive calls where each subproblem (doll) is solved itself via the same principles than the Russian Dolls Search and the application of an elimination rule allowing not to generate a significant number of dolls. Results of computational experiments show that the algorithm outperforms the best exact combinatorial algorithms in the literature for the great majority of the dense graphs tested, being more than twice faster in several cases.
△ Less
Submitted 27 May, 2015; v1 submitted 4 July, 2014;
originally announced July 2014.
-
Multi-hop Energy-efficient Control for Heterogeneous Wireless Sensor Networks Using Fuzzy Logic
Authors:
Alexandre M Melo Silva,
Christiano C Maciel,
Suelene do Carmo Correa
Abstract:
Wireless Sensor Networks (WSN) have severe energy constraints imposed by limited capacity of the internal battery of sensor nodes. These restrictions stimulate the development of energy-efficient strategies aimed at increasing the period of stability and lifetime of these networks. In this paper, we propose a centralized control to elect more appropriate Cluster Heads, assuming three levels of het…
▽ More
Wireless Sensor Networks (WSN) have severe energy constraints imposed by limited capacity of the internal battery of sensor nodes. These restrictions stimulate the development of energy-efficient strategies aimed at increasing the period of stability and lifetime of these networks. In this paper, we propose a centralized control to elect more appropriate Cluster Heads, assuming three levels of heterogeneity and multi-hop communication between Cluster Heads. The centralized control uses the k-means algorithm, responsible for the division of clusters and Fuzzy Logic to elect the Cluster Head and selecting the best route of communication. The study results indicate that the proposed approach can increase the period of stability and lifetime in WSN.
△ Less
Submitted 20 January, 2014;
originally announced January 2014.
-
Linear Time Computation of the Maximal Linear and Circular Sums of Multiple Independent Insertions into a Sequence
Authors:
Ricardo C. Corrêa,
Pablo M. S. Farias
Abstract:
The maximal sum of a sequence "A" of "n" real numbers is the greatest sum of all elements of any strictly contiguous and possibly empty subsequence of "A", and it can be computed in "O(n)" time by means of Kadane's algorithm. Letting "A^(x -> p)" denote the sequence which results from inserting a real number "x" between elements "A[p-1]" and "A[p]", we show how the maximal sum of "A^(x -> p)" can…
▽ More
The maximal sum of a sequence "A" of "n" real numbers is the greatest sum of all elements of any strictly contiguous and possibly empty subsequence of "A", and it can be computed in "O(n)" time by means of Kadane's algorithm. Letting "A^(x -> p)" denote the sequence which results from inserting a real number "x" between elements "A[p-1]" and "A[p]", we show how the maximal sum of "A^(x -> p)" can be computed in "O(1)" worst-case time for any given "x" and "p", provided that an "O(n)" time preprocessing step has already been executed on "A". In particular, this implies that, given "m" pairs "(x_0, p_0), ..., (x_{m-1}, p_{m-1})", we can compute the maximal sums of sequences "A^(x_0 -> p_0), ..., A^(x_{m-1} -> p_{m-1})" in "O(n+m)" time, which matches the lower bound imposed by the problem input size, and also improves on the straightforward strategy of applying Kadane's algorithm to each sequence "A^(x_i -> p_i)", which takes a total of "Theta(n.m)" time. Our main contribution, however, is to obtain the same time bound for the more complicated problem of computing the greatest sum of all elements of any strictly or circularly contiguous and possibly empty subsequence of "A^(x -> p)". Our algorithms are easy to implement in practice, and they were motivated by and find application in a buffer minimization problem on wireless mesh networks.
△ Less
Submitted 8 November, 2016; v1 submitted 4 July, 2013;
originally announced July 2013.
-
Insertion and Sorting in a Sequence of Numbers Minimizing the Maximum Sum of a Contiguous Subsequence
Authors:
Ricardo C. Corrêa,
Pablo M. S. Farias,
Críston P. de Souza
Abstract:
Let $A$ be a sequence of $n \geq 0$ real numbers. A subsequence of $A$ is a sequence of contiguous elements of $A$. A \emph{maximum scoring subsequence} of $A$ is a subsequence with largest sum of its elements, which can be found in O(n) time by Kadane's dynamic programming algorithm. We consider in this paper two problems involving maximal scoring subsequences of a sequence. Both of these problem…
▽ More
Let $A$ be a sequence of $n \geq 0$ real numbers. A subsequence of $A$ is a sequence of contiguous elements of $A$. A \emph{maximum scoring subsequence} of $A$ is a subsequence with largest sum of its elements, which can be found in O(n) time by Kadane's dynamic programming algorithm. We consider in this paper two problems involving maximal scoring subsequences of a sequence. Both of these problems arise in the context of buffer memory minimization in computer networks. The first one, which is called {\sc Insertion in a Sequence with Scores (ISS)}, consists in inserting a given real number $x$ in $A$ in such a way to minimize the sum of a maximum scoring subsequence of the resulting sequence, which can be easily done in $O(n^2)$ time by successively applying Kadane's algorithm to compute the maximum scoring subsequence of the resulting sequence corresponding to each possible insertion position for $x$. We show in this paper that the ISS problem can be solved in linear time and space with a more specialized algorithm. The second problem we consider in this paper is the {\sc Sorting a Sequence by Scores (SSS)} one, stated as follows: find a permutation $A'$ of $A$ that minimizes the sum of a maximum scoring subsequence. We show that the SSS problem is strongly NP-Hard and give a 2-approximation algorithm for it.
△ Less
Submitted 25 February, 2013; v1 submitted 22 October, 2012;
originally announced October 2012.
-
Variable-rate Retransmissions for Incremental Redundancy Hybrid ARQ
Authors:
Leszek Szczecinski,
Ciro Correa,
Luciano Ahumada
Abstract:
The throughput achievable in truncated Hybrid ARQ protocol (HARQ) using incremental redundancy (IR) in analyzed when transmitting over a block-fading channel whose state is unknown at the transmitter. We allow the transmission lengths to vary, optimize them efficiently via dynamic programming, and show that such a variable-rate HARQ-IR provides gains with respect to a fixed-rate transmission in te…
▽ More
The throughput achievable in truncated Hybrid ARQ protocol (HARQ) using incremental redundancy (IR) in analyzed when transmitting over a block-fading channel whose state is unknown at the transmitter. We allow the transmission lengths to vary, optimize them efficiently via dynamic programming, and show that such a variable-rate HARQ-IR provides gains with respect to a fixed-rate transmission in terms of increased throughput and decreased average number of transmissions, reducing at the same time the outage probability.
△ Less
Submitted 1 July, 2012;
originally announced July 2012.
-
Optimal k-fold colorings of webs and antiwebs
Authors:
Manoel Campêlo,
Ricardo C. Corrêa,
Phablo F. S. Moura,
Marcio C. Santos
Abstract:
A k-fold x-coloring of a graph is an assignment of (at least) k distinct colors from the set {1, 2, ..., x} to each vertex such that any two adjacent vertices are assigned disjoint sets of colors. The smallest number x such that G admits a k-fold x-coloring is the k-th chromatic number of G, denoted by χ_k(G). We determine the exact value of this parameter when G is a web or an antiweb. Our result…
▽ More
A k-fold x-coloring of a graph is an assignment of (at least) k distinct colors from the set {1, 2, ..., x} to each vertex such that any two adjacent vertices are assigned disjoint sets of colors. The smallest number x such that G admits a k-fold x-coloring is the k-th chromatic number of G, denoted by χ_k(G). We determine the exact value of this parameter when G is a web or an antiweb. Our results generalize the known corresponding results for odd cycles and imply necessary and sufficient conditions under which χ_k(G) attains its lower and upper bounds based on the clique, the fractional chromatic and the chromatic numbers. Additionally, we extend the concept of χ-critical graphs to χ_k-critical graphs. We identify the webs and antiwebs having this property, for every integer k <= 1.
△ Less
Submitted 29 August, 2011;
originally announced August 2011.
-
Musical Genres: Beating to the Rhythms of Different Drums
Authors:
Debora C. Correa,
Jose H. Saito,
Luciano da F. Costa
Abstract:
Online music databases have increased signicantly as a consequence of the rapid growth of the Internet and digital audio, requiring the development of faster and more efficient tools for music content analysis. Musical genres are widely used to organize music collections. In this paper, the problem of automatic music genre classification is addressed by exploring rhythm-based features obtained f…
▽ More
Online music databases have increased signicantly as a consequence of the rapid growth of the Internet and digital audio, requiring the development of faster and more efficient tools for music content analysis. Musical genres are widely used to organize music collections. In this paper, the problem of automatic music genre classification is addressed by exploring rhythm-based features obtained from a respective complex network representation. A Markov model is build in order to analyse the temporal sequence of rhythmic notation events. Feature analysis is performed by using two multivariate statistical approaches: principal component analysis(unsupervised) and linear discriminant analysis (supervised). Similarly, two classifiers are applied in order to identify the category of rhythms: parametric Bayesian classifier under gaussian hypothesis (supervised), and agglomerative hierarchical clustering (unsupervised). Qualitative results obtained by Kappa coefficient and the obtained clusters corroborated the effectiveness of the proposed method.
△ Less
Submitted 19 November, 2009;
originally announced November 2009.
-
A Lagrangian Relaxation for the Maximum Stable Set Problem
Authors:
Manoel Campelo,
Ricardo C. Correa
Abstract:
We propose a new integer programming formulation for the problem of finding a maximum stable set of a graph based on representatives of stable sets. In addition, we investigate exact solutions provided by a Lagrangian decomposition of this formulation in which only one constraint is relaxed. Some computational experiments were carried out with an effective multi-threaded implementation of our al…
▽ More
We propose a new integer programming formulation for the problem of finding a maximum stable set of a graph based on representatives of stable sets. In addition, we investigate exact solutions provided by a Lagrangian decomposition of this formulation in which only one constraint is relaxed. Some computational experiments were carried out with an effective multi-threaded implementation of our algorithm in a multi-core system, and their results are presented.
△ Less
Submitted 8 March, 2009;
originally announced March 2009.
-
Partially ordered distributed computations on asynchronous point-to-point networks
Authors:
Ricardo C. Correa,
Valmir C. Barbosa
Abstract:
Asynchronous executions of a distributed algorithm differ from each other due to the nondeterminism in the order in which the messages exchanged are handled. In many situations of interest, the asynchronous executions induced by restricting nondeterminism are more efficient, in an application-specific sense, than the others. In this work, we define partially ordered executions of a distributed a…
▽ More
Asynchronous executions of a distributed algorithm differ from each other due to the nondeterminism in the order in which the messages exchanged are handled. In many situations of interest, the asynchronous executions induced by restricting nondeterminism are more efficient, in an application-specific sense, than the others. In this work, we define partially ordered executions of a distributed algorithm as the executions satisfying some restricted orders of their actions in two different frameworks, those of the so-called event- and pulse-driven computations. The aim of these restrictions is to characterize asynchronous executions that are likely to be more efficient for some important classes of applications. Also, an asynchronous algorithm that ensures the occurrence of partially ordered executions is given for each case. Two of the applications that we believe may benefit from the restricted nondeterminism are backtrack search, in the event-driven case, and iterative algorithms for systems of linear equations, in the pulse-driven case.
△ Less
Submitted 30 November, 2006;
originally announced November 2006.
