1,721,151 research outputs found
Minimizing the flow time without migration
No full textWe consider the classical problem of scheduling jobs in a multiprocessor setting in order to minimize the flow time (total time in the system). The performance of the algorithm, both in online and online settings, can be significantly improved if we allow preemption, i.e., interrupt a job and later continue its execution, perhaps migrating it to a different machine. Preemption is inherent to make a scheduling algorithm efficient. While in the case of a single processor most operating systems can easily handle preemptions, migrating a job to a different machine results in a huge overhead. Thus, it is not commonly used in most multiprocessor operating systems. The natural question is whether migration is an inherent component for an efficient scheduling algorithm in either the online or online setting. Leonardi and Raz [Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, El Paso, TX, 1997, pp. 110 119] showed that the well-known algorithm, shortest remaining processing time (SRPT), performs within a logarithmic factor of the optimal online algorithm. Note that SRPT must use both preemption and migration to schedule the jobs. It is not known if better approximation factors can be reached and thus SRPT, although it is an online algorithm, becomes the best known algorithm in the online setting. In fact, in the online setting, Leonardi and Raz showed that no algorithm can achieve a better bound. Without migration, no (online or online) approximations are known. This paper introduces a new algorithm that does not use migration, works online, and is just as effective ( in terms of approximation ratio) as the best known online algorithm that uses migration
Blindly-Competitive Algorithms for Pricing & Bidding (Extended Abstract)
No full text) Baruch Awerbuch Yossi Azar y November 30, 1994 Abstract The standard setting for competitive analysis of online algorithms assumes that online algorithm knows the past (but not future) inputs, and can optimize its performance by "learning" from mistakes of the past. This framework cannot capture some of the real-life online decision-making, which takes place without full knowledge of past and present inputs. Instead, online algorithm only knows a function (or part) of its past decisions and real inputs (which we call the hidden input). A typical example is that of economic "warfare" involving, say, two companies, and a pool of (unknown) customers. In this work, we focus on problem of pricing an inter-dependent collection of resources, in the absence of knowledge about the following crucial information about the past and future inputs: ffl the customers financial benefit or prices offered by the competition, ffl the duration of the contracts, and ffl the future demand for the ..
An improved algorithm for CIOQ switches
Full text linkAbstract The problem of maximizing the weighted throughput in various switching settings has beenintensively studied recently through competitive analysis. To date, the most general model that has been investigated is the standard CIOQ (Combined Input and Output Queued) switcharchitecture with internal fabric speedup S> = 1. CIOQ switches, that comprise the backbone ofpacket routing networks, are N * N switches controlled by a switching policy that incorporatestwo components: Admission control and scheduling. An admission control strategy is essential to determine the packets stored in the FIFO queues in input and output ports, while the schedulingpolicy conducts the transfer of packets through the internal fabric, from input ports to output ports. The online problem of maximizing the total weighted throughput of CIOQ switcheswas recently investigated by Kesselman and Ros'en in [15]. They presented two different online algorithms for the general problem that achieve non-constant competitive ratios (linear in eitherthe speedup or the number of distinct values, or logarithmic in the value range). We introduce the first constant-competitive algorithm for the general case of the problem, with arbitraryspeedup and packet values. Specifically, our algorithm is 8-competitive, and is also simple and easy to implement. 1 Introduction Overview: Recently, packet routing networks have become the dominant platform for data transfer. The backbone of such networks is composed of N * N switches, that accept packets through multiple incoming connections and route them through multiple outgoing connections. As network traffic continuously increases and traffic patterns constantly change, switches routinely have to efficiently cope with overloaded traffic, and are forced to discard packets due to insufficient buffer space, while attempting to forward the more valuable packets to their destinations
Competitive On-line Selective Multicast via Dense Trees Construction (Extended Abstract)
No full text) Baruch Awerbuch 1;2 Yossi Azar 3 Rainer Gawlick 2 1 Johns Hopkins University 2 Laboratory for Computer Science, MIT 3 Tel-Aviv University May 3, 1994 Abstract This paper introduces the problem of selective online multicast and presents an log O(1) n thruput competitive solution, which handles issues of route selection and admission control, in general networks with n nodes. For each node and each multi-cast (broadcast) group, we assume that the node has an arbitrary probability with which it wishes to join the group. 1 Introduction Motivation. The introduction of fiber technology gives rise to new applications, such as interactive TV and video-conferencing, that feature multi-point communication. Applications with multi-point communication can be modeled as sources that broadcast information to subscribing nodes along a spanning (Steiner) tree. In modern networks, (e.g., ATM networks [deP91, Bou92], high-speed networks [ACG + 90, CG88, ACG91, CGG91], or private vi..
Maximal Dense Trees and Competitive On-line Selective Multicast (Extended Abstract)
No full text) Baruch Awerbuch 1;2 Yossi Azar 3 Rainer Gawlick 2 1 Johns Hopkins University 2 Laboratory for Computer Science, MIT 3 Tel-Aviv University Abstract In this paper we introduce the problem of selective multi-cast and develop the first on-line algorithm for general networks with provable performance guarantees. The essence of the problem is to maximize the number of accommodated users, in presence of bounded network resources. Our algorithm exhibits a poly-logarithmic competitive ratio in terms of the number of accepted users. The techniques and concepts used to develop the algorithm seem of interest in their own right. In particular, the new graph-theoretic concept of maximal dense subsets, introduced in this paper, motivated the first efficient approximation for the k-MST problem. Another interesting technique introduced in this paper is the aggregation of statistical information in networks, using sparse network decompositions and Chernoff bounds. 1 Introduction Motivati..
Generalized reordering buffer management
Full text linkAn instance of the generalized reordering buffer management problem consists of a service station that has k servers, each configured with a color, and a buffer of size b. The station needs to serve an online stream of colored items. Whenever an item arrives, it is stored in the buffer. At any point in time, a currently pending item can be served by switching a server to its color. The objective is to serve all items in a way that minimizes the number of servers color switches. This problem generalizes two well-studied online problems: the paging problem, which is the special case when b=1, and the reordering buffer problem, which is the special case when k=1. In this paper, we develop a randomized online algorithm that obtains a competitive ratio of O(sqrt(b).ln(k)). Note that this result beats the easy deterministic lower bound of k whenever b < k^(2-e). We complement our randomized approach by presenting a deterministic algorithm that attains a competitive ratio of O(min{k^2.ln(b),k.b}). We further demonstrate that if our deterministic algorithm can employ k/(1-d) servers where d is in (0,1), then it achieves a competitive ratio of O(min{ln(b/d^2),b/d}) against an optimal offline adversary that employs k servers
Multi Layer Peeling for Linear Arrangement and Hierarchical Clustering
Full text linkWe present a new multi-layer peeling technique to cluster points in a metric space. A well-known non-parametric objective is to embed the metric space into a simpler structured metric space such as a line (i.e., Linear Arrangement) or a binary tree (i.e., Hierarchical Clustering). Points which are close in the metric space should be mapped to close points/leaves in the line/tree; similarly, points which are far in the metric space should be far in the line or on the tree. In particular we consider the Maximum Linear Arrangement problem [Refael Hassin and Shlomi Rubinstein, 2001] and the Maximum Hierarchical Clustering problem [Vincent Cohen-Addad et al., 2018] applied to metrics.
We design approximation schemes (1-ε approximation for any constant ε > 0) for these objectives. In particular this shows that by considering metrics one may significantly improve former approximations (0.5 for Max Linear Arrangement and 0.74 for Max Hierarchical Clustering). Our main technique, which is called multi-layer peeling, consists of recursively peeling off points which are far from the "core" of the metric space. The recursion ends once the core becomes a sufficiently densely weighted metric space (i.e. the average distance is at least a constant times the diameter) or once it becomes negligible with respect to its inner contribution to the objective. Interestingly, the algorithm in the Linear Arrangement case is much more involved than that in the Hierarchical Clustering case, and uses a significantly more delicate peeling
Truthful Unsplittable Flow for Large Capacity Networks ABSTRACT
No full textThe unsplittable flow problem is one of the most extensively studied optimization problems in the field of networking. An instance of it consists of an edge capacitated graph and a set of connection requests, each of which is associated with source and target vertices, a demand, and a value. The objective is to route a maximum value subset of requests subject to the edge capacities. It is a well known fact that as the capacities of the edges are larger with respect to the maximal demand among the requests, the problem can be approximated better. In particular, it is known that for sufficiently large capacities, the integrality gap of the corresponding integer linear program becomes 1 + ɛ, whichcan be matched by an algorithm that utilizes the randomized rounding technique. In this paper, we focus our attention on the large capacities unsplittable flow problem in a game theoretic setting. In this setting, there are selfish agents, which control some of the requests characteristics, and may be dishonest about them. It is worth noting that in game theoretic settings many standard techniques, such as randomized rounding, violate certain monotonicity properties, which are imperative for truthfulness, and therefore cannot be employed. In light of this state of affairs, we design a monotone deterministic algorithm, which is based on a primal-dual machinery, e which attains an approximation ratio of e−1,uptoadisparity of ɛ away. This implies an improvement on the current best truthful mechanism, as well as an improvement on the current best combinatorial algorithm for the problem under consideration. Surprisingly, we demonstrate that any algorithm in the family of reasonable iterative path minimizing algorithms, cannot yield a better approximation ratio. Consequently, it follows that in order to achieve a mono-∗ Research supported in part by the Israel Science Foundation and by the German-Israeli Foundation. † This paper forms part of a Ph.D. thesis written by the author under the supervision of Prof. N. Alon and Prof. Y
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
- …
