1,721,126 research outputs found
On Generalized Gossiping and Broadcasting (Extended Abstract)
No full textSamir Khuller, Yoo-Ah Kim, and Yung-Chun (Justin) Wan Department of Computer Science and Institute for Advanced Computer Studies, University of Maryland, College Park, MD 20742
The Loading Time Scheduling Problem (Extended Abstract)
No full text) Randeep Bhatia Samir Khuller y Joseph (Seffi) Naor z Computer Science Department Computer Science Department Computer Science Department Univ. of Maryland Univ. of Maryland Technion College Park, MD 20742 College Park, MD 20742 Haifa 32000, Israel Abstract In this paper we study precedence constrained scheduling problems, where the tasks can only be executed on a specified subset of the machines. Each machine has a loading time that is incurred only for the first task that is scheduled on the machine in a particular run. This basic scheduling problem arises in the context of machining on numerically controlled machines, query optimization in databases, and in other artificial intelligence applications. We give the first non-trivial approximation algorithm for this problem. We also prove non-trivial lower bounds on best possible approximation ratios for these problems. These improve on the non-approximability results that are implied by the non-approximability results for the s..
Energy Efficient Scheduling via Partial Shutdown
Full text linkWe define a collection of new problems referred to as ``machine activation''
problems. The central framework we introduce considers a collection of M
machines (unrelated or related), with machine having an activation
cost of .
There is also a collection of N jobs that need to be performed, and
is the processing time of job on machine .
Standard scheduling models assume that the set of machines is fixed
and all machines are available. We assume that there is an activation cost
budget of
-- we would like to select a subset S of the machines to activate
with total cost and find a schedule for the jobs on the
machines in minimizing the makespan. In this work we develop
bi-criteria approximation algorithms for this problem based on both
LP rounding and a greedy approach
Facility Location with Dynamic Distance Functions (Extended Abstract)
No full text) Randeep Bhatia Sudipto Guha y Samir Khuller z Yoram J. Sussmann x Dept. of Computer Science University of Maryland College Park, MD 20742 Abstract Facility location problems have always been studied with the assumption that the edge lengths in the network are static and do not change over time. The underlying network could be used to model a city street network for emergency facility location/hospitals, or an electronic network for locating information centers. In any case, it is clear that due to traffic congestion the traversal time on links changes with time. Very often, we have some estimates as to how the edge lengths change over time, and our objective is to choose a set of locations (vertices) as centers, such that at every time instant each vertex has a center close to it (clearly, the center close to a vertex may change over time). We also provide approximation algorithms as well as hardness results for the K-center problem under this model. This is the first compr..
Revisiting Connected Dominating Sets: An Optimal Local Algorithm?
Full text linkIn this paper we consider the classical Connected Dominating Set (CDS) problem. Twenty years ago, Guha and Khuller developed two algorithms for this problem - a centralized greedy approach with an approximation guarantee of H(D) +2, and a local greedy approach with an approximation guarantee of 2(H(D)+1) (where H() is the harmonic function, and D is the maximum degree in the graph). A local greedy algorithm uses significantly less information about the graph, and can be useful in a variety of contexts. However, a fundamental question remained - can we get a local greedy algorithm with the same performance guarantee as the global greedy algorithm without the penalty of the multiplicative factor of "2" in the approximation factor? In this paper, we answer that question in the affirmative
Data sets used to demonstrate the software MadHitter in the manuscript "The Landscape of Receptor-Mediated Precision Cancer Combination Therapy Via a Single-Cell Perspective"
No full textThis is a zip archive of nine single-cell RNASeq data sets used in the manuscript entitled:
"The Landscape of Receptor-Mediated Precision Cancer Combination Therapy Via A Single-Cell Perspective" by Saba Ahmadi, Pattara Sukprasert, Rahulsimham Vegesna, Sanju Sinha, Fiorella Schischlik, Natalie Artzi, Samir Khuller, Alejandro A. Schaffer, Eytan Ruppin,
The README.txt describes the data sets in detail.
The associated software can be found at https://github.com/ruppinlab/madhitterFor any questions, contact Alejandro Schaffer at [email protected]
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
Variations on the Author
Full text link“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
Appropriate Similarity Measures for Author Cocitation Analysis
Full text linkWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
- …
