enter search term and/or author name
Adaptive Uncertainty Resolution in Bayesian Combinatorial Optimization Problems
Sudipto Guha, Kamesh Munagala
Article No.: 1
In several applications such as databases, planning, and sensor networks, parameters such as selectivity, load, or sensed values are known only with some associated uncertainty. The performance of such a system (as captured by some objective...
We introduce a new framework for designing online algorithms that can incorporate additional information about the input sequence, while maintaining a reasonable competitive ratio if the additional information is incorrect. Within this framework,...
Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance
Bernhard Haeupler, Telikepalli Kavitha, Rogers Mathew, Siddhartha Sen, Robert E. Tarjan
Article No.: 3
We present two online algorithms for maintaining a topological order of a directed n-vertex acyclic graph as arcs are added, and detecting a cycle when one is created. Our first algorithm handles m arc additions in...
This article presents asymptotically optimal algorithms for rectangular matrix transpose, fast Fourier transform (FFT), and sorting on computers with multiple levels of caching. Unlike previous optimal algorithms, these algorithms are cache...
Adversarial Queuing on the Multiple Access Channel
Bogdan S. Chlebus, Dariusz R. Kowalski, Mariusz A. Rokicki
Article No.: 5
We study deterministic broadcasting on multiple access channels when packets are injected continuously. The quality of service is considered in the framework of adversarial queuing. An adversary is determined by injection rate and burstiness, the...
The research in the parameterized
Improved Fixed-Parameter Algorithms for Minimum-Flip Consensus Trees
Sebastian Böcker, Quang Bao Anh Bui, Anke Truss
Article No.: 7
In computational phylogenetics, the problem of constructing a consensus tree for a given set of rooted input trees has frequently been addressed. In this article we study the
We deal with exact algorithms for