|
Acuna, V., Ferreira, C. E., Freire, A. S., & Moreno, E. (2014). Solving the maximum edge biclique packing problem on unbalanced bipartite graphs. Discret Appl. Math., 164, 2–12.
Abstract: A biclique is a complete bipartite graph. Given an (L, R)-bipartite graph G = (V, E) and a positive integer k, the maximum edge biclique packing (num') problem consists in finding a set of at most k bicliques, subgraphs of G, such that the bicliques are vertex disjoint with respect to a subset of vertices S, where S E {V, L, R}, and the number of edges inside the bicliques is maximized. The maximum edge biclique (mEs) problem is a special case of the MEBP problem in which k = 1. Several applications of the MEB problem have been studied and, in this paper, we describe applications of the MEBP problem in metabolic networks and product bundling. In these applications the input graphs are very unbalanced (i.e., IRI is considerably greater than ILI), thus we consider carefully this property in our models. We introduce a new formulation for the MEB problem and a branch-and-price scheme, using the classical branch rule by Ryan and Foster, for the MEBP problem. Finally, we present computational experiments with instances that come from the described applications and also with randomly generated instances. (C) 2011 Elsevier B.V. All rights reserved.
|
|
|
Alvarez-Miranda, E., & Pereira, J. (2022). A Districting Application with a Quality of Service Objective. Mathematics, 10(1), 13.
Abstract: E-commerce sales have led to a considerable increase in the demand for last-mile delivery companies, revealing several problems in their logistics processes. Among these problems, are not meeting delivery deadlines. For example, in Chile, the national consumer service (SERNAC) indicated that in 2018, late deliveries represented 23% of complaints in retail online sales and were the second most common reason for complaints. Some of the causes are incorrectly designed delivery zones because in many cases, these delivery zones do not account for the demographic growth of cities. The result is an imbalanced workload between different zones, which leads to some resources being idle while others fail to meet their workload in satisfactory conditions. The present work proposes a hybrid method for designing delivery zones with an objective based on improving the quality of express delivery services. The proposed method combines a preprocess based on the grouping of demand in areas according to the structure of the territory, a heuristic that generates multiple candidates for the distribution zones, and a mathematical model that combines the different distribution zones generated to obtain a final territorial design. To verify the applicability of the proposed method, a case study is considered based on the real situation of a Chilean courier company with low service fulfillment in its express deliveries. The results obtained from the computational experiments show the applicability of the method, highlighting the validity of the aggregation procedure and improvements in the results obtained using the hybrid method compared to the initial heuristic. The final solution improves the ability to meet the conditions associated with express deliveries, compared with the current situation, by 12 percentage points. The results also allow an indicative sample of the critical service factors of a company to be obtained, identifying the effects of possible changes in demand or service conditions
|
|
|
Alvarez-Miranda, E., Campos-Valdes, C., Quiroga, M. M., Moreno-Faguett, M., & Pereira, J. (2020). A Multi-Criteria Pen for Drawing Fair Districts: When Democratic and Demographic Fairness Matter. Mathematics, 8(9), 27 pp.
Abstract: Electoral systems are modified by individuals who have incentives to bias the rules for their political advantage (i.e., gerrymandering). To prevent gerrymandering, legislative institutions can rely on mathematical tools to guarantee democratic fairness and territorial contiguity. These tools have been successfully used in the past; however, there is a need to accommodate additional meanings of the term fairness within the electoral systems of modern democracies. In this paper, we present an optimization framework that considers multiple criteria for drawing districts and assigning the number of representatives. Besides some typical districting criteria (malapportionment and contiguity), we introduce novel criteria for ensuring territorial equilibrium and incentives for candidates to deploy their representation efforts fairly during their campaign and period in office. We test the method, which we denote as Multi-criteria Pen, in a recent and a forthcoming reform of the Chilean electoral system. The results show the potential of our tool to improve the current territorial design and offers insights on the motivations, objectives, and deficiencies of both reform plans.
|
|
|
Alvarez-Miranda, E., Pereira, J., Torrez-Meruvia H., & Vila, M. (2021). A Hybrid Genetic Algorithm for the Simple Assembly Line Balancing Problem with a Fixed Number of Workstations. Mathematics, 9(17), 2157.
Abstract: The assembly line balancing problem is a classical optimisation problem whose objective is to assign each production task to one of the stations on the assembly line so that the total efficiency of the line is maximized. This study proposes a novel hybrid method to solve the simple version of the problem in which the number of stations is fixed, a problem known as SALBP-2. The hybrid differs from previous approaches by encoding individuals of a genetic algorithm as instances of a modified problem that contains only a subset of the solutions to the original formulation. These individuals are decoded to feasible solutions of the original problem during fitness evaluation in which the resolution of the modified problem is conducted using a dynamic programming based approach that uses new bounds to reduce its state space. Computational experiments show the efficiency of the method as it is able to obtain several new best-known solutions for some of the benchmark instances used in the literature for comparison purposes.
|
|
|
Aracena, J., Demongeot, J., Fanchon, E., & Montalva, M. (2013). On the number of update digraphs and its relation with the feedback arc sets and tournaments. Discret Appl. Math., 161(10-11), 1345–1355.
Abstract: An update digraph corresponds to a labeled digraph that indicates a relative order of its nodes introduced to define equivalence classes of deterministic update schedules yielding the same dynamical behavior of a Boolean network. In Aracena et al. [1], the authors exhibited relationships between update digraphs and the feedback arc sets of a given digraph G. In this paper, we delve into the study of these relations. Specifically, we show differences and similarities between both sets through increasing and decreasing monotony properties in terms of their structural characteristics. Besides, we prove that these sets are equivalent if and only if all the digraph circuits are cycles. On the other hand, we characterize the minimal feedback arc sets of a given digraph in terms of their associated update digraphs. In particular, for complete digraphs, this characterization shows a close relation with acyclic tournaments. For the latter, we show that the size of the associated equivalence classes is a power of two. Finally, we determine exactly the number of update digraphs associated to digraphs containing a tournament. (C) 2013 Elsevier B.V. All rights reserved.
|
|
|
Araneda, A. A., & Villena, M. J. (2021). Computing the CEV option pricing formula using the semiclassical approximation of path integral. J. Comput. Appl. Math., 388, 113244.
Abstract: The CEV model allows volatility to change with the underlying price, capturing a basic empirical regularity very relevant for option pricing, such as the volatility smile. Nevertheless, the standard CEV solution, using the non-central chi-square approach, still presents high computational times. In this paper, the CEV option pricing formula is computed using the semiclassical approximation of Feynman's path integral. Our simulations show that the method is quite efficient and accurate compared to the standard CEV solution considering the pricing of European call options. (C) 2020 Elsevier B.V. All rights reserved.
|
|
|
Araujo, J., Ducoffe, G., Nisse, N., & Suchan, K. (2018). On interval number in cycle convexity. Discret. Math. Theor. Comput. Sci., 20(1), 35 pp.
Abstract: Recently, Araujo et al. [Manuscript in preparation, 2017] introduced the notion of Cycle Convexity of graphs. In their seminal work, they studied the graph convexity parameter called hull number for this new graph convexity they proposed, and they presented some of its applications in Knot theory. Roughly, the tunnel number of a knot embedded in a plane is upper bounded by the hull number of a corresponding planar 4-regular graph in cycle convexity. In this paper, we go further in the study of this new graph convexity and we study the interval number of a graph in cycle convexity. This parameter is, alongside the hull number, one of the most studied parameters in the literature about graph convexities. Precisely, given a graph G, its interval number in cycle convexity, denoted by in(cc)(G), is the minimum cardinality of a set S subset of V (G) such that every vertex w is an element of E V (G) \ S has two distinct neighbors u, v is an element of S such that u and v lie in same connected component of G[S], i.e. the subgraph of G induced by the vertices in S. In this work, first we provide bounds on in(cc) (G) and its relations to other graph convexity parameters, and explore its behaviour on grids. Then, we present some hardness results by showing that deciding whetherin(cc) (G) <= k is NP-complete, even if G is a split graph or a bounded-degree planar graph, and that the problem is W[2]-hard in bipartite graphs when k is the parameter. As a consequence, we obtain that in(cc) (G) cannot be approximated up to a constant factor in the classes of split graphs and bipartite graphs (unless P = NP). On the positive side, we present polynomial-time algorithms to compute in(cc) (G) for outerplanar graphs, cobipartite graphs and interval graphs. We also present fixed-parameter tractable (FPT) algorithms to compute it for (q, q – 4)-graphs when q is the parameter and for general graphs G when parameterized either by the treewidth or the neighborhood diversity of G. Some of our hardness results and positive results are not known to hold for related graph convexities and domination problems. We hope that the design of our new reductions and polynomial-time algorithms can be helpful in order to advance in the study of related graph problems.
|
|
|
Ayala, A., Claeys, X., Escapil-Inchauspé, P., & Jerez-Hanckes, C. (2022). Local Multiple Traces Formulation for electromagnetics: Stability and preconditioning for smooth geometries. J. Comput. Appl. Math., 413, 114356.
Abstract: We consider the time-harmonic electromagnetic transmission problem for the unit sphere. Appealing to a vector spherical harmonics analysis, we prove the first stability result of the local multiple traces formulation (MTF) for electromagnetics, originally introduced by Hiptmair and Jerez-Hanckes (2012) for the acoustic case, paving the way towards an extension to general piecewise homogeneous scatterers. Moreover, we investigate preconditioning techniques for the local MTF scheme and study the accumulation points of induced operators. In particular, we propose a novel second-order inverse approximation of the operator. Numerical experiments validate our claims and confirm the relevance of the preconditioning strategies.
|
|
|
Becker, F., Montealegre, P., Rapaport, I., & Todinca, I. (2020). The Impact Of Locality In The Broadcast Congested Clique Model. SIAM Discret. Math., 34(1), 682–700.
Abstract: The broadcast congested clique model (BCLIQUE) is a message-passing model of distributed computation where n nodes communicate with each other in synchronous rounds. First, in this paper we prove that there is a one-round, deterministic algorithm that reconstructs the input graph G if the graph is d-degenerate, and rejects otherwise, using bandwidth b = O(d . log n). Then, we introduce a new parameter to the model. We study the situation where the nodes, initially, instead of knowing their immediate neighbors, know their neighborhood up to a fixed radius r. In this new framework, denoted BCLIQuE[r], we study the problem of detecting, in G, an induced cycle of length at most k (CYCLE <= k) and the problem of detecting an induced cycle of length at least k +1 (CYCLE>k). We give upper and lower bounds. We show that if each node is allowed to see up to distance r = left perpendicular k/2 right perpendicular + 1, then a polylogarithmic bandwidth is sufficient for solving CYCLE>k with only two rounds. Nevertheless, if nodes were allowed to see up to distance r = left perpendicular k/3 right perpendicular, then any one-round algorithm that solves CYCLE>k needs the bandwidth b to be at least Omega(n/ log n). We also show the existence of a one-round, deterministic BCLIQUE algorithm that solves CYCLE <= k with bandwitdh b = O(n(1/left perpendicular k/2 right perpendicular). log n). On the negative side, we prove that, if epsilon <= 1/3 and 0 < r <= k/4, then any epsilon-error, R-round, b-bandwidth algorithm in the BCLIQUE[r] model that solves problem CYCLE(<= k )satisfies R . b = Omega(n(1/left perpendicular k/2 right perpendicular)).
|
|
|
Bitar, N., Goles, E., & Montealegre, P. (2022). COMPUTATIONAL COMPLEXITY OF BIASED DIFFUSION-LIMITED AGGREGATION. SIAM Discret. Math., 36(1), 823–866.
Abstract: Diffusion-Limited Aggregation (DLA) is a cluster-growth model that consists in a set of particles that are sequentially aggregated over a two-dimensional grid. In this paper, we introduce a biased version of the DLA model, in which particles are limited to move in a subset of possible directions. We denote by k-DLA the model where the particles move only in k possible directions. We study the biased DLA model from the perspective of Computational Complexity, defining two decision problems The first problem is Prediction, whose input is a site of the grid c and a sequence S of walks, representing the trajectories of a set of particles. The question is whether a particle stops at site c when sequence S is realized. The second problem is Realization, where the input is a set of positions of the grid, P. The question is whether there exists a sequence S that realizes P, i.e. all particles of S exactly occupy the positions in P. Our aim is to classify the Prediciton and Realization problems for the different versions of DLA. We first show that Prediction is P-Complete for 2-DLA (thus for 3-DLA). Later, we show that Prediction can be solved much more efficiently for 1-DLA. In fact, we show that in that case the problem is NL-Complete. With respect to Realization, we show that restricted to 2-DLA the problem is in P, while in the 1-DLA case, the problem is in L.
|
|
|
Bravo, M., & Cominetti, R. (2018). Sharp convergence rates for averaged nonexpansive maps. Isr. J. Math., 227(1), 163–188.
Abstract: We establish sharp estimates for the convergence rate of the Kranosel'skiA-Mann fixed point iteration in general normed spaces, and we use them to show that the optimal constant of asymptotic regularity is exactly . To this end we consider a nested family of optimal transport problems that provide a recursive bound for the distance between the iterates. We show that these bounds are tight by building a nonexpansive map T: [0, 1](N) -> [0, 1](N) that attains them with equality, settling a conjecture by Baillon and Bruck. The recursive bounds are in turn reinterpreted as absorption probabilities for an underlying Markov chain which is used to establish the tightness of the constant 1/root pi.
|
|
|
Bustamante, M., & Lefranc, G. (2011). Degradation Model Of Breast Imaging By Dispersed Radiation. Proc. Rom. Acad. Ser. A-Math. Phys., 12(4), 347–352.
Abstract: This paper presents a model of interaction of radiation on breast, based on Bosso's filter. This model is used to improve mammographic images for early cancer diagnosis, to be more accurate and to detect cluster of microcalcifications. The model is based on degradation of breast image produced by dispersed radiation using the Bosso's filter, developed earlier.
|
|
|
Campos-Valdes, C., Alvarez-Miranda, E., Quiroga, M. M., Pereira, J., & Duran, F. L. (2021). The Impact of Candidates' Profile and Campaign Decisions in Electoral Results: A Data Analytics Approach. Mathematics, 9(8), 902.
Abstract: In recent years, a wide range of techniques has been developed to predict electoral results and to measure the influence of different factors in these results. In this paper, we analyze the influence of the political profile of candidates (characterized by personal and political features) and their campaign effort (characterized by electoral expenditure and by territorial deployment strategies retrieved from social networks activity) on the electoral results. This analysis is carried out by using three of the most frequent data analyitcs algorithms in the literature. For our analysis, we consider the 2017 Parliamentary elections in Chile, which are the first elections after a major reform of the electoral system, that encompassed a transition from a binomial to a proportional system, a modification of the districts' structure, an increase in the number of seats, and the requirement of gender parity in the lists of the different coalitions. The obtained results reveal that, regardless of the political coalition, the electoral experience of candidates, in particular in the same seat they are running for (even when the corresponding district is modified), is by large the most influential factor to explain the electoral results. However, the attained results show that the influence of other features, such as campaign expenditures, depends on the political coalition. Additionally, by means of a simulation procedure, we show how different levels of territorial deployment efforts might impact on the results of candidates. This procedure could be used by parties and coalitions when planning their campaign strategies.
|
|
|
Casalino, G., Castellano, G., Hryniewicz, O., Leite, D., Opara, K., Radziszewska, W., et al. (2023). Semi-Supervised vs. Supervised Learning for Mental Health Monitoring: A Case Study on Bipolar Disorder. Int. J. Appl. Math. Comput. Sci., 33(3), 419–428.
Abstract: Acoustic features of speech are promising as objective markers for mental health monitoring. Specialized smartphone apps can gather such acoustic data without disrupting the daily activities of patients. Nonetheless, the psychiatric assessment of the patient's mental state is typically a sporadic occurrence that takes place every few months. Consequently, only a slight fraction of the acoustic data is labeled and applicable for supervised learning. The majority of the related work on mental health monitoring limits the considerations only to labeled data using a predefined ground-truth period. On the other hand, semi-supervised methods make it possible to utilize the entire dataset, exploiting the regularities in the unlabeled portion of the data to improve the predictive power of a model. To assess the applicability of semi-supervised learning approaches, we discuss selected state-of-the-art semi-supervised classifiers, namely, label spreading, label propagation, a semi-supervised support vector machine, and the self training classifier. We use real-world data obtained from a bipolar disorder patient to compare the performance of the different methods with that of baseline supervised learning methods. The experiment shows that semi-supervised learning algorithms can outperform supervised algorithms in predicting bipolar disorder episodes.
|
|
|
Chambolle, A., & Contreras, J. P. (2023). Accelerated Bregman Primal-Dual Methods Applied to Optimal Transport and Wasserstein Barycenter Problems. SIMODS, 4(4), 1369–1395.
Abstract: This paper discusses the efficiency of Hybrid Primal-Dual (HPD) type algorithms to approximately solve discrete Optimal Transport (OT) and Wasserstein Barycenter (WB) problems, with and without entropic regularization. Our first contribution is an analysis showing that these methods yield state-of-the-art convergence rates, both theoretically and practically. Next, we extend the HPD algorithm with the linesearch proposed by Malitsky and Pock in 2018 to the setting where the dual space has a Bregman divergence, and the dual function is relatively strongly convex to the Bregman's kernel. This extension yields a new method for OT and WB problems based on smoothing of the objective that also achieves state-of-the-art convergence rates. Finally, we introduce a new Bregman divergence based on a scaled entropy function that makes the algorithm numerically stable and reduces the smoothing, leading to sparse solutions of OT and WB problems. We complement our findings with numerical experiments and comparisons.
|
|
|
Chuaqui, M., Hamada, H., Hernandez, R., & Kohr, G. (2014). Pluriharmonic mappings and linearly connected domains in C-n. Isr. J. Math., 200(1), 489–506.
Abstract: In this paper we obtain certain sufficient conditions for the univalence of pluriharmonic mappings defined in the unit ball of C-n . The results are generalizations of conditions of Chuaqui and Hernandez that relate the univalence of planar harmonic mappings with linearly connected domains, and show how such domains can play a role in questions regarding injectivity in higher dimensions. In addition, we extend recent work of Hernandez and Martin on a shear type construction for planar harmonic mappings, by adapting the concept of stable univalence to pluriharmonic mappings of the unit ball into C-n .
|
|
|
Cominetti, R., Quattropani, M., & Scarsini, M. (2022). The Buck-Passing Game. Math. Oper. Res., Early Access.
Abstract: We consider two classes of games in which players are the vertices of a directed graph. Initially, nature chooses one player according to some fixed distribution and gives the player a buck. This player passes the buck to one of the player's out-neighbors in the graph. The procedure is repeated indefinitely. In one class of games, each player wants to minimize the asymptotic expected frequency of times that the player receives the buck. In the other class of games, the player wants to maximize it. The PageRank game is a particular case of these maximizing games. We consider deterministic and stochastic versions of the game, depending on how players select the neighbor to which to pass the buck. In both cases, we prove the existence of pure equilibria that do not depend on the initial distribution; this is achieved by showing the existence of a generalized ordinal potential. If the graph on which the game is played admits a Hamiltonian cycle, then this is the outcome of prior-five Nash equilibrium in the minimizing game. For the minimizing game, we then use the price of anarchy and stability to measure fairness of these equilibria.
|
|
|
Cominetti, R., Scarsini, M., Schroder, M., & Stier-Moses, N. (2022). Approximation and Convergence of Large Atomic Congestion Games. Math. Oper. Res., Early Access.
Abstract: We consider the question of whether and in what sense, Wardrop equilibria provide a good approximation for Nash equilibria in atomic unsplittable congestion games with a large number of small players. We examine two different definitions of small players. In the first setting, we consider games in which each player's weight is small. We prove that when the number of players goes to infinity and their weights to zero, the random flows in all (mixed) Nash equilibria for the finite games converge in distribution to the set of Wardrop equilibria of the corresponding nonatomic limit game. In the second setting, we consider an increasing number of players with a unit weight that participate in the game with a decreasingly small probability. In this case, the Nash equilibrium flows converge in total variation toward Poisson random variables whose expected values are War drop equilibria of a different nonatomic game with suitably defined costs. The latter can be viewed as symmetric equilibria in a Poisson game in the sense of Myerson, establishing a plausible connection between the Wardrop model for routing games and the stochastic fluctuations observed in real traffic. In both settings, we provide explicit approximation bounds, and we study the convergence of the price of anarchy. Beyond the case of congestion games, we prove a general result on the convergence of large games with random players toward Poisson games.
|
|
|
Concha-Vega, P., Goles, E., Montealegre, P., & Rios-Wilson, M. (2022). On the Complexity of Stable and Biased Majority. Mathematics, 10(18), 3408.
Abstract: A majority automata is a two-state cellular automata, where each cell updates its state according to the most represented state in its neighborhood. A question that naturally arises in the study of these dynamical systems asks whether there exists an efficient algorithm that can be implemented in order to compute the state configuration reached by the system at a given time-step. This problem is called the prediction problem. In this work, we study the prediction problem for a more general setting in which the local functions can be different according to their behavior in tie cases. We define two types of local rules: the stable majority and biased majority. The first one remains invariant in tie cases, and the second one takes the value 1. We call this class the heterogeneous majority cellular automata (HMCA). For this latter class, we show that in one dimension, the prediction problem for HMCA is in NL as a consequence of the dynamics exhibiting a type of bounded change property, while in two or more dimensions, the problem is P-Complete as a consequence of the capability of the system of simulating Boolean circuits.
|
|
|
Coudert, D., Luedtke, J., Moreno, E., & Priftis, K. (2018). Computing and maximizing the exact reliability of wireless backhaul networks. In Electronic Notes in Discrete Mathematics (Vol. 64, pp. 85–94).
|
|