Abstract In this paper, we propose SoftBinReduce, a data reduction method for Color Quantization. Our approach consists of four main steps: (1) identifying representatives in each channel, (2) generating three-dimensional bins, (3) distributing pixel values using a soft binning technique, and (4) repositioning the resulting bins. Additionally, we introduce an adapted Sort-Means algorithm for the Pixel Mapping phase, providing a strong initial guess. We conduct an extensive experimental evaluation primarily using the CQ100 dataset, but also the older Kodak and USC-SIPI datasets. We compare our method to two well-known data reduction techniques from the literature: pseudo-random and quasi-random sampling. The results demonstrate that our method outperforms both in terms of NMSE error versus the achieved speedup, particularly when the data is significantly reduced and with a higher number of colors in the generated palette. Moreover, an ablation study shows that all components of our method are necessary for producing high-quality results.

Every day it is more common to hear around us about the publication of studies, surveys or statistical results about the well-being of people, workers, women in a given country. Indeed, as university professors, our work cannot be independent of the level of well-being of our students. So, in this work, we propose a methodology to asses the students well-being inside a course implementation by what we call the educational well-being index (EWI). We start with a survey that gathers those factors that computing courses’ students at our university –of two different levels and majors– consider most important. Our second step is the evaluation –by a group of teachers– of the presence of those factors in different educational models of implementation of the courses. We use principal component analysis to extract, from the student data, the valuations that they expressed in the survey: the principal component of their own measurements on well-being. We work only with the coefficients of the first dimension of the principal component. The third step is a (subjective) valuation of the topics addressed in the survey when considering a particular educational model. Finally, we gather everything together to obtain a well-being index of an educational model that allows their comparison. Besides the methodology, we present and analyze the values obtained from our case study.

The Network Alignment problem is a hard Combinatorial Optimization problem with a wide range of applications, especially in computational biology. Given two (or more) networks, the goal is to find a mapping between their respective nodes that preserves the topological and functional structure of the networks. In this work we extend a novel ant colony optimization approach for network alignment by adding a recently proposed Negative Learning mechanism. In particular, information for Negative Learning is obtained by solving sub-instances of the tackled problem instances at each iteration by means of an Integer Linear Programming solver. The results show that the proposed algorithm not only outperforms the standard ant colony optimization approach but also current state-of-the-art methods from the literature.

We propose the FwLTR and BwLTR, two new centrality measures based on the Linear Threshold model. In contrast to the Linear Threshold rank (LTR), these measures differentiate between the incoming and the outgoing neighborhoods of the activation set that initiates the spreading process. Their rankings are distinguishable from the rest of the centrality measures considered traditionally. However, LTR and BwLTR behave quite similarly, while FwLTR is clearly different.

The longest arc-preserving common subsequence problem is an NP-hard combinatorial optimization problem from the field of computational biology. This problem finds applications, in particular, in the comparison of art-annotated ribonucleic acid (RNA) sequences. In this work we propose a simple, hybrid evolutionary algorithm to tackle this problem. The most important feature of this algorithm concerns a crossover operator based on solution merging. In solution merging, two or more solutions to the problem are merged, and an exact technique is used to find the best solution within this union. It is experimentally shown that the proposed algorithm outperforms a heuristic from the literature.

The most strings with few bad columns problem is an NP-hard combinatorial optimization problem from the bioinformatics field. This paper presents the first integer linear programming model for this problem. Moreover, a simple greedy heuristic and a more sophisticated extension, namely a greedy-based pilot method, are proposed. Experiments show that, as expected, the greedy-based pilot method improves over the greedy strategy. For problem instances of small and medium size the best results were obtained by solving the integer linear programming model by CPLEX, while the greedy-based pilot methods scales much better to large problem instances.

What is the role that a university should play in the spreading of cutting-edge technologies? It is argued here that one possibility is to bring focused cutting-edge technology courses in the standard curriculum. It is contended that such courses have shorter life-spans than conventional subjects and, consequently, their implementation needs to be more dynamic. These claims are backed by discussing the life-cycle of an Android course running biannually from Spring 2010 to Spring 2013 at Universitat Politecnica de Catalunya. The rise phase of this course (which lasted two semesters) was a challenging experience that motivated students and lecturers to play a cooperative and active role in the creation of true working Android applications. The course held stable for two semesters while student motivation began to fall as smart phones increasingly became everyday objects. During these two phases the course was offered as extra curricular in the undergraduate phase. Two added factors were instrumental in the decline (or fall) phase: the availability of on-line information and the fact that the course became a requirement of a master’s curriculum.

In this work we present a protocol for self-synchronized duty-cycling in wireless sensor networks with energy harvesting capabilities. The protocol is implemented in Wiselib, a library of generic algorithms for sensor networks. Simulations are conducted with the sensor network simulator Shawn. They are based on the specifications of real hardware known as iSense sensor nodes. The experimental results show that the proposed mechanism is able to adapt to changing energy availabilities. Moreover, it is shown that the system is very robust against packet loss.

The edge-disjoint paths (EDP) problem The EDP problem is interesting for different research fields such as combinatorial optimization, algorithmic graph theory and operations research. In general, there is a lack of efficient algorithms for tackling the EDP problem. Only some greedy approaches and a preliminary ant colony optimization (ACO) approach (Blesa and Blum, 2004) exist for tackling the problem. The greedy approaches are used as approximation algorithms for theoretical purposes, but the quality of the solutions they obtain are susceptible to improvement. Based on the (basic) approach in Blesa and Blum (2004), we have evolved a more sophisticated ACO algorithm

Abstract In this article, we propose several variations of the adversarial queueing model and address stability issues of networks and protocols in those proposed models. The first such variation is thepriority model, which is directed at static network topologies and takes into account the case in which packets can have different priorities. Those priorities are assigned by an adversary at injection time. A second variation, thevariable priority model, is an extension of the priority model in which the adversary may dynamically change the priority of packets at each time step. Two more variations, namely thefailure modeland thereliable model, are proposed to cope with dynamic networks. In the failure and reliable models the adversary controls, under different constraints, the failures that the links of the topology might suffer. Concerning stability of networks in the proposed adversarial models, we show that the set ofuniversally stablenetworks in the adversarial model remains the same in the priority, variable priority, failure, and reliable models. From the point of view of protocols (or queueing policies), we show that several protocols that are universally stable in the adversarial queueing model remain so in the priority, failure, and reliable models. However, we show that thelongest‐in‐system(LIS) protocol, which is universally stable in the adversarial queueing model, is not universally stable in any of the other models we propose. Moreover, we show that no queueing policy is universally stable in the variable priority model. Finally, we analyze the problem of deciding stability of a given network under a fixed protocol. We provide a characterization of the networks that are stable underfirst‐in‐first‐out(FIFO) and LIS in the failure model (and therefore in the reliable and priority models). This characterization allows us to show that the stability problem under FIFO and LIS in the failure model can be solved in polynomial time. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 45(1), 23–35 2005

We study universal stability of directed and undirected graphs in the adversarial queuing model for static packet routing. In this setting, packets are injected in some edge and have to traverse a predefined path before leaving the system. Restrictions on the allowed packet trajectory provide a way to analyze stability under different packet trajectories. We consider five packet trajectories, two for directed graphs and three for undirected graphs, and provide polynomial time algorithms for testing universal stability when considering each of them. In each case we obtain a different characterization of the universal stability property in terms of a set of forbidden subgraphs. Thus we show that variations of the allowed packet trajectory lead to nonequivalent characterizations. Using those characterizations we are also able to provide polynomial time algorithms for testing stability under the \NTGLIS (Nearest To Go-Longest In System) protocol.

In this paper we study the universal stability of undirected graphs in the adversarial queueing model for packet routing. In this setting, packets must be injected in some edge and have to traverse a path before leaving the system. Restrictions on the allowed types of path that packets must traverse provide different packet models. We consider three natural models, and provide polynomial time algorithms for testing universal stability on them. In the three cases, we obtain a different characterization, in terms of forbidden subgraphs, thus showing that slight variations lead to non-equivalent models.We extend those results to show that universal stability of digraphs, in the case in which packets follow directed paths without repeating vertices, can be decided in polynomial time.All the instability results are obtained for the \NTGLIS protocol. Therefore, the property of universal stability is equivalent to \NTGLIS-stability, in all the cases.

We present two generic parallel skeletons for the tabu search method-a well known meta-heuristic for approximately solving combinatorial optimization problems. The first skeleton is based on independent runs while the second in the classical master-slave model. Our starting point is the design and implementation of a sequential skeleton that is used later as basis for the two parallel skeletons. Both skeletons provide the user with the following: a permit to obtain parallel implementations of the tabu search method for concrete combinatorial optimization problems from existing sequential implementations; there is no need for the user to know either parallel programming or communication libraries; and the parallel implementation of tabu search for a concrete problem is obtained automatically from a sequential implementation of tabu search for the problem. The skeletons, however, require from the user a sequential instantiation of the tabu search method for the problem at hand. The skeletons are implemented in C++ using MPI as the communication library and offer genericity, flexibility, component reuse, robustness and time savings. We have instantiated the two skeletons for the 0-1 multidimensional knapsack problem, among others, for which we report computational results.