Catálogo de publicaciones - libros

Given a sequence of real numbers and two positive integers and , where , the problem is to locate disjoint segments of , each has length at least , such that their sum of densities is maximized. The best previously known algorithm, due to Bergkvist and Damaschke [1], runs in (+) time. In this paper, we give an (+log)-time algorithm.

We introduce an adaptation of run-relaxed heaps which provides efficient heap operations with respect to the number of element comparisons performed. Our data structure guarantees the worst-case cost of (1) for –, , and ; and the worst-case cost of (lg ) with at most lg + 3 lg lg + (1) element comparisons for , improving the bound of on the number of element comparisons known for run-relaxed heaps. Here, denotes the number of elements stored prior to the operation in question, and lg equals max{1, log}.

We regard the problem of communication in the presence of faulty transmissions. In contrast to the classical works in this area, we assume some structure on the times when the faults occur. More realistic seems the “burst error model”, in which all faults occur in some small time interval.

Like previous work, our problem can best be modelled as a two-player perfect information game, in which one player (“Paul”) has to guess a number from {1, ..., } using Yes/No-questions, which the second player (“Carole”) has to answer truthfully apart from few lies. In our setting, all lies have to be in a consecutive set of rounds.

We show that (for big ) Paul needs roughly log+loglog+ rounds to determine the number, which is only more than the case of just one single lie.

We study Small–World graphs in the perspective of their use in the development of efficient as well as easy to implement network infrastructures. Our analysis starts from the Small–World model proposed by Kleinberg: a grid network augmented with directed long–range random links. The choices of the long–range links are independent from one node to another. In this setting greedy routing and some of its variants have been analyzed and shown to produce paths of polylogarithmic expected length. We start from asking whether all the independence assumed in the Kleinberg’s model among long–range contacts of different nodes is indeed necessary to assure the existence of short paths. In order to deal with the above question, we impose (stringent) restrictions on the choice of long–range links and we show that such restrictions do not increase the average path length of greedy routing and of its variations. Diminishing the randomness in the choice of random links has several benefits; in particular, it implies an increase in the clustering of the graph, thus increasing the resilience of the network.

We study the communication primitives of broadcasting (one-to-all communication) and gossiping (all-to-all communication) in known topology radio networks, i.e., where for each primitive the schedule of transmissions is precomputed based on full knowledge about the size and the topology of the network. We show that gossiping can be completed in time units in any radio network of size , diameter and maximum degree Δ= Ω(log). This is an almost optimal schedule in the sense that there exists a radio network topology, such as: a Δ-regular tree in which the radio gossiping cannot be completed in less than units of time. Moreover, we show a schedule for the broadcast task. Both our transmission schemes significantly improve upon the currently best known schedules in Gąsieniec, Peleg and Xin [PODC’05], i.e., a (+Δlog) time schedule for gossiping and a +(log) time schedule for broadcast. Our broadcasting schedule also improves, for large , a very recent (+log) time broadcasting schedule by Kowalski and Pelc.

One of the most frequently studied problems in the context of information dissemination in communication networks is the broadcasting problem. In this paper, we study the following randomized broadcasting protocol. At some time an information is placed at one of the nodes of a graph. In the succeeding steps, each informed node chooses one neighbor, independently and uniformly at random, and informs this neighbor by sending a copy of to it.

In this work, we develop tight bounds on the runtime of the algorithm described above, and analyze its robustness. First, it is shown that on Δ-regular graphs this algorithm requires at least rounds to inform all nodes. For general graphs, we prove a slightly weaker lower bound and improve the upper bound of Feige et. al. [8] to (1+(1)) ln which implies that is the worst-case graph. Furthermore, we determine the worst-case-ratio between the runtime of a fastest deterministic algorithm and the randomized one.

This paper also contains an investigation of the robustness of this broadcasting algorithm against random node failures. We show that if the informed nodes are allowed to fail in some step with probability 1–, then the broadcasting time increases by a factor of at most 6/. Finally, the previous result is applied to state some asymptotically optimal upper bounds for the runtime of randomized broadcasting in Cartesian products of graphs and to determine the performance of agent based broadcasting [6] in graphs with good expansion properties.

A popular approach in the design of evolutionary algorithms is to integrate local search into the random search process. These so-called memetic algorithms have demonstrated their efficiency in countless applications covering a wide area of practical problems. However, theory of memetic algorithms is still in its infancy and there is a strong need for a rigorous theoretical foundation to better understand these heuristics. Here, we attack one of the fundamental issues in the design of memetic algorithms from a theoretical perspective, namely the choice of the frequency with which local search is applied. Since no guidelines are known for the choice of this parameter, we care about its impact on memetic algorithm performance. We present worst-case problems where the local search frequency has an enormous impact on the performance of a simple memetic algorithm. A rigorous theoretical analysis shows that on these problems, with overwhelming probability, even a small factor of 2 decides about polynomial versus exponential optimization times.

We study a general class of non-cooperative games coming from combinatorial covering and facility location problems. A game for players is based on an integer programming formulation. Each player wants to satisfy a subset of the constraints. Variables represent resources, which are available in costly integer units and must be bought. The cost can be shared arbitrarily between players. Once a unit is bought, it can be used by all players to satisfy their constraints. In general the cost of pure-strategy Nash equilibria in this game can be prohibitively high, as both prices of anarchy and stability are in Θ(). In addition, deciding the existence of pure Nash equilibria is NP-hard. These results extend to recently studied single-source connection games. Under certain conditions, however, cheap Nash equilibria exist: if the integrality gap of the underlying integer program is 1 and in the case of single constraint players. In addition, we present algorithms that compute cheap approximate Nash equilibria in polynomial time.

In this paper we consider the problem of locating a path-shaped or tree-shaped (extensive) facility in trees under the condition that existing facilities are already located. We introduce a parametric-pruning method to solve the conditional extensive weighted 1-center location problems in trees in linear time. This improves the recent results of ( log) by Tamir et al. [16].

We provide an improved FPTAS for multiobjective shortest paths, a fundamental (NP-hard) problem in multiobjective optimization, along with a new generic method for obtaining FPTAS to multiobjective optimization problem with objectives. We show how these results can be used to obtain better approximate solutions to three related problems that have important applications in QoS routing and in traffic optimization.