Given two (di)graphs G, H and a cost function $c:V(G)\times V(H) \to \mathbb{Q}_{\geq 0}\cup\{+\infty\}$, in the minimum cost homomorphism problem, MinHOM(H), goal is finding a homomorphism $f:V(G)\to V(H)$ (a.k.a H-coloring) that minimizes $\sum\limits_{v\in V(G)}c(v,f(v))$. The complexity of exact minimization of this problem is well understood [34], and the class of digraphs H, for which the MinHOM(H) is polynomial time solvable is a small subset of all digraphs. In this paper, we consider the approximation of MinHOM within a constant factor. For digraphs, MinHOM(H) is not approximable if H contains a digraph asteroidal triple (DAT). We take a major step toward a dichotomy classification of approximable cases. We give a dichotomy classification for approximating the MinHOM(H) when H is a graph. For digraphs, we provide constant factor approximation algorithms for two important classes of digraphs, namely bi-arc digraphs (digraphs with a conservative semi-lattice polymorphism or min-ordering), and k-arc digraphs (digraphs with an extended min-ordering). Specifically, we show that: 1. Dichotomy for Graphs: MinHOM(H) has a $2|V(H)|$-approximation algorithm if graph H admits a conservative majority polymorphims (i.e. H is a bi-arc graph), otherwise, it is inapproximable; 2. MinHOM(H) has a $|V(H)|^2$-approximation algorithm if H is a bi-arc digraph; 3. MinHOM(H) has a $|V(H)|^2$-approximation algorithm if H is a k-arc digraph. In conclusion, we show the importance of these results and provide insights for achieving a dichotomy classification of approximable cases. Our constant factors depend on the size of H. However, the implementation of our algorithms provides a much better approximation ratio. It leaves open to investigate a classification of digraphs H, where MinHOM(H) admits a constant factor approximation algorithm that is independent of H.

In the last decade, it has become apparent that the performance of Pareto-dominance-based evolutionary multiobjective optimization algorithms degrades as the number of objective functions of the problem, given by n, grows. This performance degradation has been the subject of several studies in the last years, but the exact mechanism behind this phenomenon has not been fully understood yet. This paper presents an analytical study of this phenomenon under problems with continuous variables, by a simple setup of quadratic objective functions with spherical contour curves and a symmetrical arrangement of the function minima location. Within such a setup, some analytical formulas are derived to describe the probability of the optimization progress as a function of the distance λ to the exact Pareto-set. A main conclusion is stated about the nature and structure of the performance degradation phenomenon in many-objective problems: when a current solution reaches a λ that is an order of magnitude smaller than the length of the Pareto-set, the probability of finding a new point that dominates the current one is given by a power law function of λ with exponent (n - 1). The dimension of the space of decision variables has no influence on that exponent. Those results give support to a discussion about some general directions that are currently under consideration within the research community.

In multiobjective optimization problems, Pareto dominance-based search techniques are known to lose their efficiency in problems with a large number of objective functions - the many-objective problems. This paper proposes an algorithm based on a stochastic differential equation approach combined with an evolutionary strategy for dealing with such problems. The proposed algorithm is intended to both allow the determination of tight Pareto-optimal solutions in many-objective problems (which is a difficult task for usual evolutionary algorithms) and to find a solution set that performs a relatively uniform sampling of the Pareto-optimal set (which is a deficiency of the known stochastic differential equation approach). The proposed algorithm is shown to attain such goals at a relatively low computational cost.

We present the architecture, user interface and prototype implementation of fluid voice, a proximity based mobile group communication system for opportunistic social exchanges. It is designed for coordinating people in outdoor settings, spreading news during emergency responses and supporting impromptu social exchanges by exploiting the inherent broadcast nature of wireless and mobility of people. It supports diverse media: live audio, asynchronous audio, text messages, audio messages, audio polls and wish lists. In this paper, we focus on the audio support and the design for intermittent connectivity characteristics of mobile systems with limited range. Users can transition from live to asynchronous audio communication in a fluid manner depending on the wireless environment. When every node is able to hear each other, the receiver mixes all sources and provides the user with a "push to listen" interface to "tune in" to who they want to listen to. When the wireless channel is congested, it transitions to a "push to talk" interface (without taking over the whole channel) to reduce collisions while allowing people to barge in. When nodes cannot hear each other, Fluid Voice caches content for future delivery using a dynamic multi-stream mixer with time shifting (Tivo) functionality. The system was prototyped on the Nokia N810's for real world testing and we discuss its technical and social limitations.