enter search term and/or author name
Fast sparse matrix multiplication
Raphael Yuster, Uri Zwick
Let A and B two n×n matrices over a ring R (e.g., the reals or the integers) each containing at most m nonzero elements. We present a new algorithm that multiplies A and B using...
A maiden analysis of longest wait first
Jeff Edmonds, Kirk Pruhs
We consider server scheduling strategies to minimize average flow time in a multicast pull system where data items have uniform size. The algorithm Longest Wait First (LWF) always services the page where the aggregate waiting times of the outstanding...
Fixed-parameter algorithms for (k, r)-center in planar graphs and map graphs
Erik D. Demaine, Fedor V. Fomin, Mohammadtaghi Hajiaghayi, Dimitrios M. Thilikos
The (k, r)-center problem asks whether an input graph G has ≤k vertices (called centers) such that every vertex of G is within distance ≤r from some center. In this article, we prove that...
Pricing multicasting in more flexible network models
Micah Adler, Dan Rubenstein
The problem of designing efficient algorithms for sharing the cost of multicasting has recently received considerable attention. In this article, we examine the effect on the complexity of pricing when two flexibility-enhancing mechanisms are...
On network design problems: fixed cost flows and the covering steiner problem
Guy Even, Guy Kortsarz, Wolfgang Slany
Network design problems, such as generalizations of the Steiner Tree Problem, can be cast as edge-cost-flow problems. An edge-cost flow problem is a min-cost flow problem in which the cost of the flow equals the sum of the costs of the edges carrying...
Black box for constant-time insertion in priority queues (note)
Stephen Alstrup, Thore Husfeldt, Theis Rauhe, Mikkel Thorup
We present a simple black box that takes a priority queue Q which supports find-min, insert, and delete in x-time at most t. Here x-time may be worst-case, expected, or amortized. The black-box transforms Q into a priority queue...
A linear-time approximation algorithm for weighted matchings in graphs
Doratha E. Drake Vinkemeier, Stefan Hougardy
Approximation algorithms have so far mainly been studied for problems that are not known to have polynomial time algorithms for solving them exactly. Here we propose an approximation algorithm for the weighted matching problem in graphs which can be...
Analysis of linear combination algorithms in cryptography
Peter J. Grabner, Clemens Heuberger, Helmut Prodinger, Jörg M. Thuswaldner
Several cryptosystems rely on fast calculations of linear combinations in groups. One way to achieve this is to use joint signed binary digit expansions of small “weight.” We study two algorithms, one based on nonadjacent forms of the...
On a generalization of the stable roommates problem
Katarína Cechlárová, Tamás Fleiner
We consider two generalizations of the stable roommates problem: a) we allow parallel edges in the underlying graph, and b) we study a problem with multiple partners. We reduce both problems to the classical stable roommates problem and describe an...
The NP-completeness column
David S. Johnson
This is the 24th edition of a column that covers new developments in the theory of NP-completeness. The presentation is modeled on that which M. R. Garey and I used in our book “Computers and Intractability: A Guide to the Theory of...