Truthful Approximation Mechanisms for Scheduling Selfish Related Machines

We consider the problem of scheduling jobs on related machines owned by selfish agents. We provide a 5-approximation deterministic truthful mechanism, the first deterministic truthful result for the problem. Previously, Archer and Tardos showed a 2-approximation randomized mechanism which is truthful in expectation only (a weaker notion of truthfulness). In case the number of machines is constant, we provide a deterministic Fully Polynomial-Time Approximation Scheme (FPTAS) and a suitable payment scheme that yields a truthful mechanism for the problem. This result, which is based on converting FPTAS to monotone FPTAS, improves a previous result of Auletta et al., who showed a (4 + ε)-approximation truthful mechanism.     

Terminally ill patients and volunteer support: Is it the right intervention?

Comments on the article by K. T. Herbst-Damm and J. A. Kulik (see record 2005-02260-012) entitled Volunteer support, marital status, and the survival times of terminally ill patients. Can a simple and low-cost intervention, such as a visit by a volunteer, extend the life of terminally ill patients? The answer, according to a study by Herbst-Damm and Kulik (2005), is yes. When it comes to quality of life, however, the effects of volunteer visits remain murky. Thus, it is critical that we look beyond effects on longevity and assess how such a program would influence quality of life. Extending the life of terminally ill patients might not always a blessing. Prolonging their life might even cause harm, as it can extend unwanted physical and mental suffering. It may also go against some patients' desire to hasten their death. Despite Herbst-Damm and Kulik's important findings, the current author remains unconvinced as to the merits of implementing volunteer visits as an intervention policy. (PsycINFO Database Record (c) 2010 APA, all rights reserved)     

Randomized range-maxima in nearly-constant parallel time

Given an array ofn input numbers, therange-maxima problem is that of preprocessing the data so that queries of the type what is the maximum value in subarray [i..j] can be answered quickly using one processor. We present a randomized preprocessing algorithm that runs inO(log^* n) time with high probability, using an optimal number of processors on a CRCW PRAM; each query can be processed in constant time by one processor. We also present a randomized algorithm for a parallel comparison model. Using an optimal number of processors, the preprocessing algorithm runs inO( (n)) time with high probability; each query can be processed inO ( (n)) time by one processor. (As is standard, (n) is the inverse of Ackermann function.) A constant time query can be achieved by some slowdown in the performance of the preprocessing stage.     

Edge detection and characterization of digitized images

Pattern Analysis and Applications - We present a method for determining which of a large set of pixels are inside or on the boundary of a polygon. The method works much quicker than the standard...     

Buffer Management for Colored Packets with Deadlines

We consider buffer management of unit packets with deadlines for a multi-port device with reconfiguration overhead. The goal is to maximize the throughput of the device, i.e., the number of packets delivered by their deadline. For a single port or with free reconfiguration, the problem reduces to the well-known packets scheduling problem, where the celebrated earliest-deadline-first (EDF) strategy is optimal 1-competitive. However, EDF is not 1-competitive when there is a reconfiguration overhead. We design an online algorithm that achieves a competitive ratio of 1−o(1) when the ratio between the minimum laxity of the packets and the number of ports tends to infinity. This is one of the rare cases where one can design an almost 1-competitive algorithm. One ingredient of our analysis, which may be interesting on its own right, is a perturbation theorem on EDF for the classical packets scheduling problem. Specifically, we show that a small perturbation in the release and deadline times cannot significantly degrade the optimal throughput. This implies that EDF is robust in the sense that its throughput is close to the optimum even when the deadlines are not precisely known.     

A Preemptive Algorithm for Maximizing Disjoint Paths on Trees

We consider the on-line version of the maximum vertex disjoint path problem when the underlying network is a tree. In this problem, a sequence of requests arrives in an on-line fashion, where every request is a path in the tree. The on-line algorithm may accept a request only if it does not share a vertex with a previously accepted request. The goal is to maximize the number of accepted requests. It is known that no on-line algorithm can have a competitive ratio better than Ω(log n) for this problem, even if the algorithm is randomized and the tree is simply a line. Obviously, it is desirable to beat the logarithmic lower bound. Adler and Azar (Proc. of the 10th ACM-SIAM Symposium on Discrete Algorithm, pp. 1–10, 1999) showed that if preemption is allowed (namely, previously accepted requests may be discarded, but once a request is discarded it can no longer be accepted), then there is a randomized on-line algorithm that achieves constant competitive ratio on the line. In the current work we present a randomized on-line algorithm with preemption that has constant competitive ratio on any tree. Our results carry over to the related problem of maximizing the number of accepted paths subject to a capacity constraint on vertices (in the disjoint path problem this capacity is 1). Moreover, if the available capacity is at least 4, randomization is not needed and our on-line algorithm becomes deterministic.     

Regularizing Flows over Lie Groups

In this paper we discuss regularization of images that take their value in matrix Lie groups. We describe an image as a section in a principal bundle which is a fibre bundle where the fiber (the feature space) is a Lie group. Via the scalar product on the Lie algebra, we define a bi-invariant metric on the Lie-group manifold. Thus, the fiber becomes a Riemannian manifold with respect to this metric. The induced metric from the principal bundle to the image manifold is obtained by means of the bi-invariant metric. A functional over the space of sections, i.e., the image manifolds, is defined. The resulting equations of motion generate a flow which evolves the sections in the spatial-Lie-group manifold. We suggest two different approaches to treat this functional and the corresponding PDEs. In the first approach we derive a set of coupled PDEs for the local coordinates of the Lie-group manifold. In the second approach a coordinate-free framework is proposed where the PDE is defined directly with respect to the Lie-group elements. This is a parameterization-free method. The differences between these two methods are discussed. We exemplify this framework on the well-known orientation diffusion problem, namely, the unit-circle S ¹ which is identified with the group of rotations in two dimensions, SO(2). Regularization of the group of rotations in 3D and 4D, SO(3) and SO(4), respectively, is demonstrated as well.

Online dynamic graph drawing

This paper presents an algorithm for drawing a sequence of graphs online. The algorithm strives to maintain the global structure of the graph and thus the user's mental map, while allowing arbitrary modifications between consecutive layouts. The algorithm works online and uses various execution culling methods in order to reduce the layout time and handle large dynamic graphs. Techniques for representing graphs on the GPU allow a speedup by a factor of up to 17 compared to the CPU implementation. The scalability of the algorithm across GPU generations is demonstrated. Applications of the algorithm to the visualization of discussion threads in Internet sites and to the visualization of social networks are provided.     

Efficient pebbling for list traversal synopses with application to program rollback

We show how to support efficient back traversal in a unidirectional list, using small memory and with essentially no slowdown in forward steps. Using O(lgn)$O(lgn)$ memory for a list of size n$n$, the i$i$’th back-step from the farthest point reached so far takes O(lgi)$O(lgi)$ time in the worst case, while the overhead per forward step is at most ?$?$ for arbitrary small constant ?>0$?>0$. An arbitrary sequence of forward and back steps is allowed. A full trade-off between memory usage and time per back-step is presented: k$k$ vs. kn^1/k$k{n}^{1/k}$ and vice versa. Our algorithms are based on a novel pebbling technique which moves pebbles on a virtual binary, or n^1/k$n^{1/k}$-ary, tree that can only be traversed in a pre-order fashion.