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.     

Molecular follow-up of disease progression and interferon therapy in chronic myelocytic leukemia

We previously reported that the abl promoter (Pa) undergoes de novo DNA methylation in the course of chronic myelocytic leukemia (CML). The clinical implications of this finding are the subject of the present study in which samples of CML patients, including a group treated with interferon alpha (IFNalpha) were surveyed. The methylation status of the abl promoter was monitored by polymerase chain reaction (PCR) amplification of the Pa region after digestion with several site-methylation sensitive restriction enzymes. Some 74% of the DNA samples from blood and marrow drawn in the chronic phase were nonmethylated, similar to control samples from non-CML patients. The remaining 26% were partially methylated in the abl Pa region. The latter samples were derived from patients who were indistinguishable from the others on the basis of clinical presentation. Methylated samples were mostly derived from patients known to have a disease of longer duration (26 months v 7.5 months, P = .01). Samples of 30 IFNalpha-treated patients were sequentially analyzed in the course of treatment. Fifteen patients with no evidence of Pa methylation before treatment remained methylation-free. The remainder, who displayed Pa methylation before treatment, reverted to the methylation-free status. The outcome is attributed to IFNalpha therapy, as the Pa methylation status was not reversed in any of the patients treated with hydroxyurea. Methylation of the abl promoter indicates a disease of long-standing, most likely associated with a higher probability of imminent blastic transformation. It appears to predict the outcome of IFNalpha therapy far better than the cytogenetic response.     

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...     

Single Nanoparticle Magnetic Spin Memristor

There is an increasing demand for the development of a simple Si‐based universal memory device at the nanoscale that operates at high frequencies. Spin‐electronics (spintronics) can, in principle, increase the efficiency of devices and allow them to operate at high frequencies. A primary challenge for reducing the dimensions of spintronic devices is the requirement for high spin currents. To overcome this problem, a new approach is presented that uses helical chiral molecules exhibiting spin‐selective electron transport, which is called the chiral‐induced spin selectivity (CISS) effect. Using the CISS effect, the active memory device is miniaturized for the first time from the micrometer scale to 30 nm in size, and this device presents memristor‐like nonlinear logic operation at low voltages under ambient conditions and room temperature. A single nanoparticle, along with Au contacts and chiral molecules, is sufficient to function as a memory device. A single ferromagnetic nanoplatelet is used as a fixed hard magnet combined with Au contacts in which the gold contacts act as soft magnets due to the adsorbed chiral molecules.     

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.     

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.     

Management of Multi-Queue Switches in QoS Networks

The concept of Quality of Service (QoS) networks has gained growing attention recently, as the traffic volume in the Internet constantly increases, and QoS guarantees are essential to ensure proper operation of most communication-based applications. A QoS switch serves m incoming queues by transmitting packets arriving to these queues through one output port, one packet per time step. Each packet is marked with a value indicating its priority in the network. Since the queues have bounded capacities and the rate of arriving packets can be much higher than the transmission rate, packets can be lost due to insufficient queue space. The goal is to maximize the total value of transmitted packets. This problem encapsulates two dependent questions: buffer management, namely which packets to admit into the queues, and scheduling, i.e. which queue to use for transmission in each time step. We use competitive analysis to study online switch performance in QoS-based networks. Specifically, we provide a novel generic technique that decouples the buffer management and scheduling problems. Our technique transforms any single-queue buffer management policy (preemptive or non-preemptive) to a scheduling and buffer management algorithm for our general m queues model, whose competitive ratio is at most twice the competitive ratio of the given buffer management policy. We use our technique to derive concrete algorithms for the general preemptive and non-preemptive cases, as well as for the interesting special cases of the 2-value model and the unit-value model. We also provide a 1.58-competitive randomized algorithm for the unit-value case. This case is interesting by itself since most current networks (e.g. IP networks) do not yet incorporate full QoS capabilities, and treat all packets equally.