Catálogo de publicaciones - libros

Firefighting is a combinatorial optimization problem on graphs that models the problem of determining the optimal strategy to contain a fire and save as much from the fire as possible. We introduce and study a new version of firefighting, , which exhibits more locality than the classical one-firefighter version. We prove that this locality allows us to develop an ()-time algorithm on trees, where is the number of nodes initially on fire. We further prove that Politician’s Firefighting is NP-hard on planar graphs of degree at most 5. We present an (+ 4)-time algorithm for this problem on general graphs, where is the number of nodes that burn using the optimal strategy, thereby proving that it is fixed-parameter tractable. We present experimental results that show that our algorithm’s search-tree size is in practice much smaller than the worst-case bound of 4.

Ant Colony Optimization (ACO) has become quite popular in recent years. In contrast to many successful applications, the theoretical foundation of this randomized search heuristic is rather weak. Building up such a theory is demanded to understand how these heuristics work as well as to come up with better algorithms for certain problems. Up to now, only convergence results have been achieved showing that optimal solutions can be obtained in finite time. We present the first runtime analysis of an ACO algorithm, which transfers many rigorous results on the runtime of a simple evolutionary algorithm to our algorithm. Moreover, we examine the choice of the evaporation factor, a crucial parameter in ACO algorithms, in detail for a toy problem. By deriving new lower bounds on the tails of sums of independent Poisson trials, we determine the effect of the evaporation factor almost completely and prove a phase transition from exponential to polynomial runtime.

Alice and Bob want to know if two strings of length are almost equal. That is, do they differ on bits? Let 0≤≤–1. We show that any deterministic protocol, as well as any error-free quantum protocol ( version), for this problem requires at least –2 bits of communication. We show the same bounds for the problem of determining if two strings differ in bits. We also prove a lower bound of /2–1 for error-free quantum protocols. Our results are obtained by employing basic tools from combinatorics and calculus to lower-bound the ranks of the appropriate matrices.

Graph states have become a key class of states within quantum computation. They form a basis for universal quantum computation, capture key properties of entanglement, are related to quantum error correction, establish links to graph theory, violate Bell inequalities, and have elegant and short graph-theoretical descriptions. We give here a rigorous analysis of the resources required for producing graph states. Using a novel graph-contraction procedure, we show that any graph state can be prepared by a linear-size constant-depth quantum circuit, and we establish trade-offs between depth and width. We show that any minimal-width quantum circuit requires gates that acts on several qubits, regardless of the depth. We relate the complexity of preparing graph states to a new graph-theoretical concept, the local minimum degree, and show that it captures basic properties of graph states.

We consider the problem of route discovery in a mesh network with faulty nodes. The number and the positions of the faulty nodes are unknown. It is known that a flooding strategy like expanding ring search can route a message linear in the minimum number of steps while it causes a traffic (i.e. the total number of messages) of . For optimizing traffic a single-path strategy is optimal producing traffic , where is the number of nodes that are adjacent to faulty nodes. We present a deterministic multi-path online routing algorithm that delivers a message within time steps causing traffic . This algorithm is asymptotically as fast as flooding and nearly traffic-optimal up to a polylogarithmic factor.

Based on some results of the on-line -truck problem with cost minimization, a realistic model of the on-line -truck problem with benefit maximization is proposed. In the model, the object of optimization is how to design on-line algorithms to maximize the benefit of all trucks’ moving. In this paper, after the model’s establishment, several on-line algorithms, e.g., Position Maintaining Strategy, Partial Greedy Algorithm, are employed to address the problem. The analyses concerning the competitive ratios of the algorithms are given in detail. Furthermore, the lower bound of competitive ratio is discussed.

We consider the problem of computing broadcast schedules for a speed-controlled channel minimizing overall energy consumption. Each request defines a strict deadline and we assume that sending at some speed for time units consumes energy . For the case that the server holds a single message and the speed of a broadcast needs to be fixed when it is started, we present an -competitive deterministic online algorithm and prove that this is asymptotically best possible even allowing randomization. For the multi-message case we prove that an extension of our algorithm is (4–1)-competitive if the lengths of requests vary by at most a factor of . Allowing the speed of running broadcasts to be changed, we give lower bounds that are still exponential in .

The concept of Oblivious Routing for general undirected networks was introduced by Räcke [12] when he showed that there exists an oblivious routing algorithm with polylogarithmic competitive ratio (w.r.t. edge congestion) for any undirected graph. In a following result, Räcke and Rosén [13] presented admission control algorithms achieving a polylogarithmic fraction (in the size of the network) of the optimal number of accepted messages. Both these results assume that the network incurs a cost only after it is accepted and the message is routed. Admission control and routing algorithms for sensor networks under energy constraints, however, need to account for the energy spent in checking for feasible routes prior to the acceptance of a message and hence, it is unclear if these algorithms achieve polylogarithmic bounds under this condition. In this paper, we address this problem and prove that such algorithms do not exist when messages are generated by an adversary. Furthermore, we show that an oblivious routing algorithm cannot have a polylogarithmic competitive ratio without a packet-admission protocol. We present a deterministic (log)-competitive algorithm for tree networks where the capacity of any node is in [,]. For grids, we present an (log)-competitive algorithm when nodes have capacities in Θ(log) under the assumption that each message is drawn uniformly at random from all pairs of nodes in the grid.

Intensity-modulated radiation therapy (IMRT) is a modern cancer treatment technique that delivers prescribed radiation dose distributions, called (IMs), to target tumors via the help of a device called the (MLC). Due to the of the MLCs, IMs whose widths exceed a given threshold cannot be delivered as a whole, and thus must be split into multiple subfields. Field splitting problems in IMRTnormally aim to minimize the total beam-on time (i.e., the total time when a patient is exposed to actual radiation during the delivery) of the resulting subfields. In this paper, we present efficient polynomial time algorithms for two general field splitting problems with guaranteed output optimality. Our algorithms are based on interesting observations and analysis, as well as new techniques and modelings. We formulate the first field splitting problem as a special integer linear programming (ILP) problem that can be solved by linear programming due to its geometry; from an optimal integer solution for the ILP, we compute an optimal field splitting by solving a set of shortest path problems on graphs. We tackle the second field splitting problem by using a novel technique on IMs.

In this paper, we present a theoretical study of several geometric shape approximation problems, called , which arise in (IMRT). Given a piecewise linear function such that () ≥0 for any ∈ℝ, the SR problems seek an optimal set of to approximate under a certain error criterion, such that the sum of the resulting constant window functions equals (or well approximates) . A constant window function () is defined on an interval such that () is a fixed value >0 for any ∈ and is 0 otherwise. Geometrically, a constant window function can be viewed as a rectangle (or a ). The SR problems find applications in micro-MLC scheduling and dose calculation of the IMRT treatment planning process, and are closely related to some well studied geometric problems. The SR problems are NP-hard, and thus we aim to develop theoretically efficient and provably good quality approximation SR algorithms. Our main results include a polynomial time -approximation algorithm for a general key SR problem and an efficient dynamic programming algorithm for an important SR case that has been studied in medical literature. Our key ideas include the following. (1) We show that a crucial subproblem of the key SR problem can be reduced to the multicommodity demand flow (MDF) problem on a path graph (which has a known (2+)-approximation algorithm); further, by extending the result of the known (2+)-approximation MDF algorithm, we develop a polynomial time -approximation algorithm for our first target SR problem. (2) We show that the second target SR problem can be formulated as a -MST problem on a certain geometric graph ; based on a set of interesting geometric observations and a non-trivial dynamic programming scheme, we are able to compute an optimal -MST in efficiently.