enter search term and/or author name
New hardness results for congestion minimization and machine scheduling
Julia Chuzhoy, Joseph (Seffi) Naor
We study the approximability of two natural NP-hard problems. The first problem is congestion minimization in directed networks. In this problem, we are given a directed graph and a set of source-sink pairs. The goal is to route all the pairs...
Finding a maximum likelihood tree is hard
Benny Chor, Tamir Tuller
Maximum likelihood (ML) is an increasingly popular optimality criterion for selecting evolutionary trees [Felsenstein 1981]. Finding optimal ML trees appears to be a very hard computational task, but for tractable cases, ML is the method of choice....
Logarithmic hardness of the undirected edge-disjoint paths problem
Matthew Andrews, Lisa Zhang
We show that there is no log⅓ − ϵ M approximation for the undirected Edge-Disjoint Paths problem unless NP ⊆ ZPTIME(npolylog(n)), where M is the size of the graph...
Combining expert advice in reactive environments
Daniela Pucci De Farias, Nimrod Megiddo
“Experts algorithms” constitute a methodology for choosing actions repeatedly, when the rewards depend both on the choice of action and on the unknown current state of the environment. An experts algorithm has access to a set of...
Using expander graphs to find vertex connectivity
Harold N. Gabow
The (vertex) connectivity κ of a graph is the smallest number of vertices whose deletion separates the graph or makes it trivial. We present the fastest known algorithm for finding κ. For a digraph with n vertices, m edges...
Online algorithms for market clearing
Avrim Blum, Tuomas Sandholm, Martin Zinkevich
In this article, we study the problem of online market clearing where there is one commodity in the market being bought and sold by multiple buyers and sellers whose bids arrive and expire at different times. The auctioneer is faced with an online...