Showing 1–24 of 24 results for author: Correa, R

Efficient Path Query Processing in Relational Database Systems

Authors: Diego Rivera Correa, Mirek Riedewald

Abstract: Path queries are crucial for property graphs, and there is growing interest in queries that combine regular expressions over labels with constraints on property values of vertices and edges. Efficient evaluation of such general path queries requires that intermediate results be eliminated early when there is no possible completion to a full result path. Neither state-of-the-art (SOA) graph DBMS no… ▽ More Path queries are crucial for property graphs, and there is growing interest in queries that combine regular expressions over labels with constraints on property values of vertices and edges. Efficient evaluation of such general path queries requires that intermediate results be eliminated early when there is no possible completion to a full result path. Neither state-of-the-art (SOA) graph DBMS nor relational DBMS currently can do this effectively for a large class of queries. We show that this problem can be addressed by giving a relational optimizer ``a little help'' by specifying early filtering opportunities explicitly in the query. To this end, we propose ReCAP, an abstraction that greatly simplifies the implementation of early filtering techniques for any type of property constraint for which such early filtering can be derived. No matter how complex the constraint, one only needs to implement (1) an NFA-style state transition function and (2) a handful of functions that mirror those needed for user-defined aggregates. We show that when using ReCAP, a standard relational DBMS like DuckDB can effectively push property constraints deep into the query plan, beating the SOA graph and relational DBMS by a factor up to 400,000 over a variety of queries and input graphs. △ Less

Submitted 2 April, 2026; originally announced April 2026.

SelfTTS: cross-speaker style transfer through explicit embedding disentanglement and self-refinement using self-augmentation

Authors: Lucas H. Ueda, João G. T. Lima, Pedro R. Corrêa, Flávio O. Simões, Mário U. Neto, Paula D. P. Costa

Abstract: This paper presents SelfTTS, a text-to-speech (TTS) model designed for cross-speaker style transfer that eliminates the need for external pre-trained speaker or emotion encoders. The architecture achieves emotional expressivity in neutral speakers through an explicit disentanglement strategy utilizing Gradient Reversal Layers (GRL) combined with cosine similarity loss to decouple speaker and emoti… ▽ More This paper presents SelfTTS, a text-to-speech (TTS) model designed for cross-speaker style transfer that eliminates the need for external pre-trained speaker or emotion encoders. The architecture achieves emotional expressivity in neutral speakers through an explicit disentanglement strategy utilizing Gradient Reversal Layers (GRL) combined with cosine similarity loss to decouple speaker and emotion information. We introduce Multi Positive Contrastive Learning (MPCL) to induce clustered representations of speaker and emotion embeddings based on their respective labels. Furthermore, SelfTTS employs a self-refinement strategy via Self-Augmentation, exploiting the model's voice conversion capabilities to enhance the naturalness of synthesized speech. Experimental results demonstrate that SelfTTS achieves superior emotional naturalness (eMOS) and robust stability in target timbre and emotion compared to state-of-the-art baselines. △ Less

Submitted 23 March, 2026; originally announced March 2026.

Comments: Submitted to Interspeech 2026

DiversityOne: A Multi-Country Smartphone Sensor Dataset for Everyday Life Behavior Modeling

Authors: Matteo Busso, Andrea Bontempelli, Leonardo Javier Malcotti, Lakmal Meegahapola, Peter Kun, Shyam Diwakar, Chaitanya Nutakki, Marcelo Dario Rodas Britez, Hao Xu, Donglei Song, Salvador Ruiz Correa, Andrea-Rebeca Mendoza-Lara, George Gaskell, Sally Stares, Miriam Bidoglia, Amarsanaa Ganbold, Altangerel Chagnaa, Luca Cernuzzi, Alethia Hume, Ronald Chenu-Abente, Roy Alia Asiku, Ivan Kayongo, Daniel Gatica-Perez, Amalia de Götzen, Ivano Bison , et al. (1 additional authors not shown)

Abstract: Understanding everyday life behavior of young adults through personal devices, e.g., smartphones and smartwatches, is key for various applications, from enhancing the user experience in mobile apps to enabling appropriate interventions in digital health apps. Towards this goal, previous studies have relied on datasets combining passive sensor data with human-provided annotations or self-reports. H… ▽ More Understanding everyday life behavior of young adults through personal devices, e.g., smartphones and smartwatches, is key for various applications, from enhancing the user experience in mobile apps to enabling appropriate interventions in digital health apps. Towards this goal, previous studies have relied on datasets combining passive sensor data with human-provided annotations or self-reports. However, many existing datasets are limited in scope, often focusing on specific countries primarily in the Global North, involving a small number of participants, or using a limited range of pre-processed sensors. These limitations restrict the ability to capture cross-country variations of human behavior, including the possibility of studying model generalization, and robustness. To address this gap, we introduce DiversityOne, a dataset which spans eight countries (China, Denmark, India, Italy, Mexico, Mongolia, Paraguay, and the United Kingdom) and includes data from 782 college students over four weeks. DiversityOne contains data from 26 smartphone sensor modalities and 350K+ self-reports. As of today, it is one of the largest and most diverse publicly available datasets, while featuring extensive demographic and psychosocial survey data. DiversityOne opens the possibility of studying important research problems in ubiquitous computing, particularly in domain adaptation and generalization across countries, all research areas so far largely underexplored because of the lack of adequate datasets. △ Less

Submitted 5 February, 2025; originally announced February 2025.

Generalization and Personalization of Mobile Sensing-Based Mood Inference Models: An Analysis of College Students in Eight Countries

Authors: Lakmal Meegahapola, William Droz, Peter Kun, Amalia de Gotzen, Chaitanya Nutakki, Shyam Diwakar, Salvador Ruiz Correa, Donglei Song, Hao Xu, Miriam Bidoglia, George Gaskell, Altangerel Chagnaa, Amarsanaa Ganbold, Tsolmon Zundui, Carlo Caprini, Daniele Miorandi, Alethia Hume, Jose Luis Zarza, Luca Cernuzzi, Ivano Bison, Marcelo Rodas Britez, Matteo Busso, Ronald Chenu-Abente, Can Gunel, Fausto Giunchiglia , et al. (2 additional authors not shown)

Abstract: Mood inference with mobile sensing data has been studied in ubicomp literature over the last decade. This inference enables context-aware and personalized user experiences in general mobile apps and valuable feedback and interventions in mobile health apps. However, even though model generalization issues have been highlighted in many studies, the focus has always been on improving the accuracies… ▽ More Mood inference with mobile sensing data has been studied in ubicomp literature over the last decade. This inference enables context-aware and personalized user experiences in general mobile apps and valuable feedback and interventions in mobile health apps. However, even though model generalization issues have been highlighted in many studies, the focus has always been on improving the accuracies of models using different sensing modalities and machine learning techniques, with datasets collected in homogeneous populations. In contrast, less attention has been given to studying the performance of mood inference models to assess whether models generalize to new countries. In this study, we collected a mobile sensing dataset with 329K self-reports from 678 participants in eight countries (China, Denmark, India, Italy, Mexico, Mongolia, Paraguay, UK) to assess the effect of geographical diversity on mood inference models. We define and evaluate country-specific (trained and tested within a country), continent-specific (trained and tested within a continent), country-agnostic (tested on a country not seen on training data), and multi-country (trained and tested with multiple countries) approaches trained on sensor data for two mood inference tasks with population-level (non-personalized) and hybrid (partially personalized) models. We show that partially personalized country-specific models perform the best yielding area under the receiver operating characteristic curve (AUROC) scores of the range 0.78-0.98 for two-class (negative vs. positive valence) and 0.76-0.94 for three-class (negative vs. neutral vs. positive valence) inference. Overall, we uncover generalization issues of mood inference models to new countries and how the geographical similarity of countries might impact mood inference. △ Less

Submitted 5 November, 2022; originally announced November 2022.

Comments: ACM IMWUT 2022, To be presented at ACM Ubicomp 2023

The EMory BrEast imaging Dataset (EMBED): A Racially Diverse, Granular Dataset of 3.5M Screening and Diagnostic Mammograms

Authors: Jiwoong J. Jeong, Brianna L. Vey, Ananth Reddy, Thomas Kim, Thiago Santos, Ramon Correa, Raman Dutt, Marina Mosunjac, Gabriela Oprea-Ilies, Geoffrey Smith, Minjae Woo, Christopher R. McAdams, Mary S. Newell, Imon Banerjee, Judy Gichoya, Hari Trivedi

Abstract: Developing and validating artificial intelligence models in medical imaging requires datasets that are large, granular, and diverse. To date, the majority of publicly available breast imaging datasets lack in one or more of these areas. Models trained on these data may therefore underperform on patient populations or pathologies that have not previously been encountered. The EMory BrEast imaging D… ▽ More Developing and validating artificial intelligence models in medical imaging requires datasets that are large, granular, and diverse. To date, the majority of publicly available breast imaging datasets lack in one or more of these areas. Models trained on these data may therefore underperform on patient populations or pathologies that have not previously been encountered. The EMory BrEast imaging Dataset (EMBED) addresses these gaps by providing 3650,000 2D and DBT screening and diagnostic mammograms for 116,000 women divided equally between White and African American patients. The dataset also contains 40,000 annotated lesions linked to structured imaging descriptors and 61 ground truth pathologic outcomes grouped into six severity classes. Our goal is to share this dataset with research partners to aid in development and validation of breast AI models that will serve all patients fairly and help decrease bias in medical AI. △ Less

Submitted 8 February, 2022; originally announced February 2022.

Two-step adversarial debiasing with partial learning -- medical image case-studies

Authors: Ramon Correa, Jiwoong Jason Jeong, Bhavik Patel, Hari Trivedi, Judy W. Gichoya, Imon Banerjee

Abstract: The use of artificial intelligence (AI) in healthcare has become a very active research area in the last few years. While significant progress has been made in image classification tasks, only a few AI methods are actually being deployed in hospitals. A major hurdle in actively using clinical AI models currently is the trustworthiness of these models. More often than not, these complex models are… ▽ More The use of artificial intelligence (AI) in healthcare has become a very active research area in the last few years. While significant progress has been made in image classification tasks, only a few AI methods are actually being deployed in hospitals. A major hurdle in actively using clinical AI models currently is the trustworthiness of these models. More often than not, these complex models are black boxes in which promising results are generated. However, when scrutinized, these models begin to reveal implicit biases during the decision making, such as detecting race and having bias towards ethnic groups and subpopulations. In our ongoing study, we develop a two-step adversarial debiasing approach with partial learning that can reduce the racial disparity while preserving the performance of the targeted task. The methodology has been evaluated on two independent medical image case-studies - chest X-ray and mammograms, and showed promises in bias reduction while preserving the targeted performance. △ Less

Submitted 16 November, 2021; originally announced November 2021.

Reading Race: AI Recognises Patient's Racial Identity In Medical Images

Authors: Imon Banerjee, Ananth Reddy Bhimireddy, John L. Burns, Leo Anthony Celi, Li-Ching Chen, Ramon Correa, Natalie Dullerud, Marzyeh Ghassemi, Shih-Cheng Huang, Po-Chih Kuo, Matthew P Lungren, Lyle Palmer, Brandon J Price, Saptarshi Purkayastha, Ayis Pyrros, Luke Oakden-Rayner, Chima Okechukwu, Laleh Seyyed-Kalantari, Hari Trivedi, Ryan Wang, Zachary Zaiman, Haoran Zhang, Judy W Gichoya

Abstract: Background: In medical imaging, prior studies have demonstrated disparate AI performance by race, yet there is no known correlation for race on medical imaging that would be obvious to the human expert interpreting the images. Methods: Using private and public datasets we evaluate: A) performance quantification of deep learning models to detect race from medical images, including the ability of… ▽ More Background: In medical imaging, prior studies have demonstrated disparate AI performance by race, yet there is no known correlation for race on medical imaging that would be obvious to the human expert interpreting the images. Methods: Using private and public datasets we evaluate: A) performance quantification of deep learning models to detect race from medical images, including the ability of these models to generalize to external environments and across multiple imaging modalities, B) assessment of possible confounding anatomic and phenotype population features, such as disease distribution and body habitus as predictors of race, and C) investigation into the underlying mechanism by which AI models can recognize race. Findings: Standard deep learning models can be trained to predict race from medical images with high performance across multiple imaging modalities. Our findings hold under external validation conditions, as well as when models are optimized to perform clinically motivated tasks. We demonstrate this detection is not due to trivial proxies or imaging-related surrogate covariates for race, such as underlying disease distribution. Finally, we show that performance persists over all anatomical regions and frequency spectrum of the images suggesting that mitigation efforts will be challenging and demand further study. Interpretation: We emphasize that model ability to predict self-reported race is itself not the issue of importance. However, our findings that AI can trivially predict self-reported race -- even from corrupted, cropped, and noised medical images -- in a setting where clinical experts cannot, creates an enormous risk for all model deployments in medical imaging: if an AI model secretly used its knowledge of self-reported race to misclassify all Black patients, radiologists would not be able to tell using the same data the model has access to. △ Less

Submitted 21 July, 2021; originally announced July 2021.

MSC Class: 68-XX ACM Class: I.2

Spatial-And-Context aware (SpACe) "virtual biopsy" radiogenomic maps to target tumor mutational status on structural MRI

Authors: Marwa Ismail, Ramon Correa, Kaustav Bera, Ruchika Verma, Anas Saeed Bamashmos, Niha Beig, Jacob Antunes, Prateek Prasanna, Volodymyr Statsevych, Manmeet Ahluwalia, Pallavi Tiwari

Abstract: With growing emphasis on personalized cancer-therapies,radiogenomics has shown promise in identifying target tumor mutational status on routine imaging (i.e. MRI) scans. These approaches fall into 2 categories: (1) deep-learning/radiomics (context-based), using image features from the entire tumor to identify the gene mutation status, or (2) atlas (spatial)-based to obtain likelihood of gene mutat… ▽ More With growing emphasis on personalized cancer-therapies,radiogenomics has shown promise in identifying target tumor mutational status on routine imaging (i.e. MRI) scans. These approaches fall into 2 categories: (1) deep-learning/radiomics (context-based), using image features from the entire tumor to identify the gene mutation status, or (2) atlas (spatial)-based to obtain likelihood of gene mutation status based on population statistics. While many genes (i.e. EGFR, MGMT) are spatially variant, a significant challenge in reliable assessment of gene mutation status on imaging has been the lack of available co-localized ground truth for training the models. We present Spatial-And-Context aware (SpACe) "virtual biopsy" maps that incorporate context-features from co-localized biopsy site along with spatial-priors from population atlases, within a Least Absolute Shrinkage and Selection Operator (LASSO) regression model, to obtain a per-voxel probability of the presence of a mutation status (M+ vs M-). We then use probabilistic pair-wise Markov model to improve the voxel-wise prediction probability. We evaluate the efficacy of SpACe maps on MRI scans with co-localized ground truth obtained from corresponding biopsy, to predict the mutation status of 2 driver genes in Glioblastoma: (1) EGFR (n=91), and (2) MGMT (n=81). When compared against deep-learning (DL) and radiomic models, SpACe maps obtained training and testing accuracies of 90% (n=71) and 90.48% (n=21) in identifying EGFR amplification status,compared to 80% and 71.4% via radiomics, and 74.28% and 65.5% via DL. For MGMT status, training and testing accuracies using SpACe were 88.3% (n=61) and 71.5% (n=20), compared to 52.4% and 66.7% using radiomics,and 79.3% and 68.4% using DL. Following validation,SpACe maps could provide surgical navigation to improve localization of sampling sites for targeting of specific driver genes in cancer. △ Less

Submitted 17 June, 2020; originally announced June 2020.

Can tumor location on pre-treatment MRI predict likelihood of pseudo-progression versus tumor recurrence in Glioblastoma? A feasibility study

Authors: Marwa Ismail, Virginia Hill, Volodymyr Statsevych, Evan Mason, Ramon Correa, Prateek Prasanna, Gagandeep Singh, Kaustav Bera, Rajat Thawani, Anant Madabhushi, Manmeet Ahluwalia, Pallavi Tiwari

Abstract: A significant challenge in Glioblastoma (GBM) management is identifying pseudo-progression (PsP), a benign radiation-induced effect, from tumor recurrence, on routine imaging following conventional treatment. Previous studies have linked tumor lobar presence and laterality to GBM outcomes, suggesting that disease etiology and progression in GBM may be impacted by tumor location. Hence, in this fea… ▽ More A significant challenge in Glioblastoma (GBM) management is identifying pseudo-progression (PsP), a benign radiation-induced effect, from tumor recurrence, on routine imaging following conventional treatment. Previous studies have linked tumor lobar presence and laterality to GBM outcomes, suggesting that disease etiology and progression in GBM may be impacted by tumor location. Hence, in this feasibility study, we seek to investigate the following question: Can tumor location on treatment-naïve MRI provide early cues regarding likelihood of a patient developing pseudo-progression versus tumor recurrence? In this study, 74 pre-treatment Glioblastoma MRI scans with PsP (33) and tumor recurrence (41) were analyzed. First, enhancing lesion on Gd-T1w MRI and peri-lesional hyperintensities on T2w/FLAIR were segmented by experts and then registered to a brain atlas. Using patients from the two phenotypes, we construct two atlases by quantifying frequency of occurrence of enhancing lesion and peri-lesion hyperintensities, by averaging voxel intensities across the population. Analysis of differential involvement was then performed to compute voxel-wise significant differences (p-value<0.05) across the atlases. Statistically significant clusters were finally mapped to a structural atlas to provide anatomic localization of their location. Our results demonstrate that patients with tumor recurrence showed prominence of their initial tumor in the parietal lobe, while patients with PsP showed a multi-focal distribution of the initial tumor in the frontal and temporal lobes, insula, and putamen. These preliminary results suggest that lateralization of pre-treatment lesions towards certain anatomical areas of the brain may allow to provide early cues regarding assessing likelihood of occurrence of pseudo-progression from tumor recurrence on MRI scans. △ Less

Submitted 16 June, 2020; originally announced June 2020.

Prophet Inequalities for I.I.D. Random Variables from an Unknown Distribution

Authors: José R. Correa, Paul Dütting, Felix Fischer, Kevin Schewior

Abstract: A central object in optimal stopping theory is the single-choice prophet inequality for independent, identically distributed random variables: Given a sequence of random variables $X_1,\dots,X_n$ drawn independently from a distribution $F$, the goal is to choose a stopping time $τ$ so as to maximize $α$ such that for all distributions $F$ we have… ▽ More A central object in optimal stopping theory is the single-choice prophet inequality for independent, identically distributed random variables: Given a sequence of random variables $X_1,\dots,X_n$ drawn independently from a distribution $F$, the goal is to choose a stopping time $τ$ so as to maximize $α$ such that for all distributions $F$ we have $\mathbb{E}[X_τ] \geq α\cdot \mathbb{E}[\max_tX_t]$. What makes this problem challenging is that the decision whether $τ=t$ may only depend on the values of the random variables $X_1,\dots,X_t$ and on the distribution $F$. For quite some time the best known bound for the problem was $α\geq1-1/e\approx0.632$ [Hill and Kertz, 1982]. Only recently this bound was improved by Abolhassani et al. [2017], and a tight bound of $α\approx0.745$ was obtained by Correa et al. [2017]. The case where $F$ is unknown, such that the decision whether $τ=t$ may depend only on the values of the first $t$ random variables but not on $F$, is equally well motivated (e.g., [Azar et al., 2014]) but has received much less attention. A straightforward guarantee for this case of $α\geq1/e\approx0.368$ can be derived from the solution to the secretary problem. Our main result is that this bound is tight. Motivated by this impossibility result we investigate the case where the stopping time may additionally depend on a limited number of samples from~$F$. An extension of our main result shows that even with $o(n)$ samples $α\leq 1/e$, so that the interesting case is the one with $Ω(n)$ samples. Here we show that $n$ samples allow for a significant improvement over the secretary problem, while $O(n^2)$ samples are equivalent to knowledge of the distribution: specifically, with $n$ samples $α\geq1-1/e\approx0.632$ and $α\leq\ln(2)\approx0.693$, and with $O(n^2)$ samples $α\geq0.745-ε$ for any $ε>0$. △ Less

Submitted 7 April, 2021; v1 submitted 14 November, 2018; originally announced November 2018.

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.

Comments: 22 pages, 4 figures

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.

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.

Fare Evasion in Transit Networks

Authors: José R. Correa, Tobias Harks, Vincent J. C. Kreuzen, Jannik Matuschke

Abstract: Public transit systems in urban areas usually require large state subsidies, primarily due to high fare evasion rates. In this paper, we study new models for optimizing fare inspection strategies in transit networks based on bilevel programming. In the first level, the leader (the network operator) determines probabilities for inspecting passengers at different locations, while in the second level… ▽ More Public transit systems in urban areas usually require large state subsidies, primarily due to high fare evasion rates. In this paper, we study new models for optimizing fare inspection strategies in transit networks based on bilevel programming. In the first level, the leader (the network operator) determines probabilities for inspecting passengers at different locations, while in the second level, the followers (the fare-evading passengers) respond by optimizing their routes given the inspection probabilities and travel times. To model the followers' behavior we study both a non-adaptive variant, in which passengers select a path a priori and continue along it throughout their journey, and an adaptive variant, in which they gain information along the way and use it to update their route. For these problems, which are interesting in their own right, we design exact and approximation algorithms and we prove a tight bound of 3/4 on the ratio of the optimal cost between adaptive and non-adaptive strategies. For the leader's optimization problem, we study a fixed-fare and a flexible-fare variant, where ticket prices may or may not be set at the operator's will. For the latter variant, we design an LP based approximation algorithm. Finally, using a local search procedure that shifts inspection probabilities within an initially determined support set, we perform an extensive computational study for all variants of the problem on instances of the Dutch railway and the Amsterdam subway network. This study reveals that our solutions are within 95% of theoretical upper bounds drawn from the LP relaxation. △ Less

Submitted 12 May, 2014; originally announced May 2014.

TSP Tours in Cubic Graphs: Beyond 4/3

Authors: José R. Correa, Omar Larré, José A. Soto

Abstract: After a sequence of improvements Boyd, Sitters, van der Ster, and Stougie proved that any 2-connected graph whose n vertices have degree 3, i.e., a cubic 2-connected graph, has a Hamiltonian tour of length at most (4/3)n, establishing in particular that the integrality gap of the subtour LP is at most 4/3 for cubic 2-connected graphs and matching the conjectured value of the famous 4/3 conjecture.… ▽ More After a sequence of improvements Boyd, Sitters, van der Ster, and Stougie proved that any 2-connected graph whose n vertices have degree 3, i.e., a cubic 2-connected graph, has a Hamiltonian tour of length at most (4/3)n, establishing in particular that the integrality gap of the subtour LP is at most 4/3 for cubic 2-connected graphs and matching the conjectured value of the famous 4/3 conjecture. In this paper we improve upon this result by designing an algorithm that finds a tour of length (4/3 - 1/61236)n, implying that cubic 2-connected graphs are among the few interesting classes of graphs for which the integrality gap of the subtour LP is strictly less than 4/3. With the previous result, and by considering an even smaller epsilon, we show that the integrality gap of the TSP relaxation is at most 4/3 - epsilon, even if the graph is not 2-connected (i.e. for cubic connected graphs), implying that the approximability threshold of the TSP in cubic graphs is strictly below 4/3. Finally, using similar techniques we show, as an additional result, that every Barnette graph admits a tour of length at most (4/3 - 1/18)n. △ Less

Submitted 7 October, 2013; originally announced October 2013.

Comments: 23 pages. A preliminary version appeared in ESA 2012

Independent and Hitting Sets of Rectangles Intersecting a Diagonal Line : Algorithms and Complexity

Authors: José R. Correa, Laurent Feuilloley, Pablo Pérez-Lantero, José A. Soto

Abstract: Finding a maximum independent set (MIS) of a given fam- ily of axis-parallel rectangles is a basic problem in computational geom- etry and combinatorics. This problem has attracted significant atten- tion since the sixties, when Wegner conjectured that the corresponding duality gap, i.e., the maximum possible ratio between the maximum independent set and the minimum hitting set (MHS), is bounded b… ▽ More Finding a maximum independent set (MIS) of a given fam- ily of axis-parallel rectangles is a basic problem in computational geom- etry and combinatorics. This problem has attracted significant atten- tion since the sixties, when Wegner conjectured that the corresponding duality gap, i.e., the maximum possible ratio between the maximum independent set and the minimum hitting set (MHS), is bounded by a universal constant. An interesting special case, that may prove use- ful to tackling the general problem, is the diagonal-intersecting case, in which the given family of rectangles is intersected by a diagonal. Indeed, Chepoi and Felsner recently gave a factor 6 approximation algorithm for MHS in this setting, and showed that the duality gap is between 3/2 and 6. In this paper we improve upon these results. First we show that MIS in diagonal-intersecting families is NP-complete, providing one smallest subclass for which MIS is provably hard. Then, we derive an $O(n^2)$-time algorithm for the maximum weight independent set when, in addition the rectangles intersect below the diagonal. This improves and extends a classic result of Lubiw, and amounts to obtain a 2-approximation algo- rithm for the maximum weight independent set of rectangles intersecting a diagonal. Finally, we prove that for diagonal-intersecting families the duality gap is between 2 and 4. The upper bound, which implies an approximation algorithm of the same factor, follows from a simple com- binatorial argument, while the lower bound represents the best known lower bound on the duality gap, even in the general case. △ Less

Submitted 3 January, 2014; v1 submitted 25 September, 2013; originally announced September 2013.

Comments: 26 pages

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.

Comments: 13 pages, 4 figures, 2 tables. Accepted for journal publication

Free Instrument for Movement Measure

Authors: Norberto Peña, Bruno Cecílio Credidio, Lorena Peixoto Nogueira Rodriguez Martinez Salles Corrêa, Lucas Gabriel Souza França, Marcelo do Vale Cunha, Marcos Cavalcanti de Sousa, João Paulo Bomfim Cruz Vieira, José Garcia Vivas Miranda

Abstract: This paper presents the validation of a computational tool that serves to obtain continuous measurements of moving objects. The software uses techniques of computer vision, pattern recognition and optical flow, to enable tracking of objects in videos, generating data trajectory, velocity, acceleration and angular movement. The program was applied to track a ball around a simple pendulum. The metho… ▽ More This paper presents the validation of a computational tool that serves to obtain continuous measurements of moving objects. The software uses techniques of computer vision, pattern recognition and optical flow, to enable tracking of objects in videos, generating data trajectory, velocity, acceleration and angular movement. The program was applied to track a ball around a simple pendulum. The methodology used to validate it, taking as a basis to compare the values measured by the program, as well as the theoretical values expected according to the model of a simple pendulum. The experiment is appropriate to the method because it was built within the limits of the linear harmonic oscillator and energy losses due to friction had been minimized, making it the most ideal possible. The results indicate that the tool is sensitive and accurate. Deviations of less than a millimeter to the extent of the trajectory, ensures the applicability of the software on physics, whether in research or in teaching topics. △ Less

Submitted 29 June, 2013; originally announced July 2013.

Comments: Accepted for publication at the RBEF - Revista Brasileira de Ensino de Física

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.

Comments: This paper has been submitted for journal publication

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.

Comments: A short version of this paper was presented at the Simpósio Brasileiro de Pesquisa Operacional, Brazil, 2011

Journal ref: Discrete Applied Mathematics, 161(1-2), pages 60-70, 2013

Inner Product Spaces for MinSum Coordination Mechanisms

Authors: Richard Cole, José R. Correa, Vasilis Gkatzelis, Vahab Mirrokni, Neil Olver

Abstract: We study policies aiming to minimize the weighted sum of completion times of jobs in the context of coordination mechanisms for selfish scheduling problems. Our goal is to design local policies that achieve a good price of anarchy in the resulting equilibria for unrelated machine scheduling. To obtain the approximation bounds, we introduce a new technique that while conceptually simple, seems to b… ▽ More We study policies aiming to minimize the weighted sum of completion times of jobs in the context of coordination mechanisms for selfish scheduling problems. Our goal is to design local policies that achieve a good price of anarchy in the resulting equilibria for unrelated machine scheduling. To obtain the approximation bounds, we introduce a new technique that while conceptually simple, seems to be quite powerful. With this method we are able to prove the following results. First, we consider Smith's Rule, which orders the jobs on a machine in ascending processing time to weight ratio, and show that it achieves an approximation ratio of 4. We also demonstrate that this is the best possible for deterministic non-preemptive strongly local policies. Since Smith's Rule is always optimal for a given assignment, this may seem unsurprising, but we then show that better approximation ratios can be obtained if either preemption or randomization is allowed. We prove that ProportionalSharing, a preemptive strongly local policy, achieves an approximation ratio of 2.618 for the weighted sum of completion times, and an approximation ratio of 2.5 in the unweighted case. Again, we observe that these bounds are tight. Next, we consider Rand, a natural non-preemptive but randomized policy. We show that it achieves an approximation ratio of at most 2.13; moreover, if the sum of the weighted completion times is negligible compared to the cost of the optimal solution, this improves to π/2. Finally, we show that both ProportionalSharing and Rand induce potential games, and thus always have a pure Nash equilibrium (unlike Smith's Rule). This also allows us to design the first \emph{combinatorial} constant-factor approximation algorithm minimizing weighted completion time for unrelated machine scheduling that achieves a factor of 2+ εfor any ε> 0. △ Less

Submitted 22 December, 2010; v1 submitted 9 October, 2010; originally announced October 2010.

Comments: 24 pages

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.

Comments: Submitted to International Transactions on Operations Research

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.

Journal ref: Parallel Computing 35 (2009), 12-28