Journal: Algorithmica

Found 758 papers in total
Combinatorial algorithms for unsplittable flow problem
Combinatorial algorithms for unsplittable flow problem
2006,
We provide combinatorial algorithms for the unsplittable flow problem (UFP) that...
Minimizing makespan and preemption costs on a system of uniform machines
Minimizing makespan and preemption costs on a system of uniform machines
2005,
It is well known that for preemptive scheduling on uniform machines there exist...
The k-splittable flow problem
The k-splittable flow problem
2005,
In traditional multi-commodity flow theory, the task is to send a certain amount of...
Improved approximations for tour and tree covers
Improved approximations for tour and tree covers
2003,
A tree (tour) cover of an edge-weighted graph is a set of edges which forms a tree...
Approximation algorithms for a capacitated network design problem
Approximation algorithms for a capacitated network design problem
2003,
We study a capacitated network design problem with applications in local access...
A cut-based algorithm for the nonlinear dual of the minimum cost network flow problem
A cut-based algorithm for the nonlinear dual of the minimum cost network flow problem
2004,
We consider a convex, or nonlinear, separable minimization problem with constraints...
Simple on-line algorithms for the maximum disjoint paths problem
Simple on-line algorithms for the maximum disjoint paths problem
2004,
In this paper we study the classical problem of finding disjoint paths in graphs. This...
A branch-checking algorithm for all-pairs shortest paths
A branch-checking algorithm for all-pairs shortest paths
2004,
We formulate and study an algorithm for all-pairs shortest paths in a network with n...
Average-case competitive analyses for ski-rental problems
Average-case competitive analyses for ski-rental problems
2005,
Let s be the ratio of the cost for purchasing skis over the cost for renting them....
Minimizing mean completion time in a batch processing system
Minimizing mean completion time in a batch processing system
2004,
We consider batch processing jobs to minimize the mean completion time. A batch...
Approximation schemes for scheduling on uniformly related and identical parallel machines
Approximation schemes for scheduling on uniformly related and identical parallel machines
2004,
We give a polynomial approximation scheme for the problem of scheduling on uniformly...
Scheduling malleable parallel tasks: An asymptotic fully polynomial time approximation scheme
Scheduling malleable parallel tasks: An asymptotic fully polynomial time approximation scheme
2004,
A malleable parallel task is one whose execution time is a function of the number of...
Minimizing makespan in batch machine scheduling
Minimizing makespan in batch machine scheduling
2004,
We study the scheduling of a set of n jobs, each characterized by a release (arrival)...
Online and offline algorithms for the time-dependent traveling salesman problem with time zones
Online and offline algorithms for the time-dependent traveling salesman problem with time zones
2004,
The time-dependent traveling salesman problem (TDTSP) is a variant of TSP with...
New approximation results for the maximum scatter traveling salesperson problem
New approximation results for the maximum scatter traveling salesperson problem
2005,
We consider the following maximum scatter traveling salesperson problem (TSP): given...
Algorithms for minimizing response time in broadcast scheduling
Algorithms for minimizing response time in broadcast scheduling
2004,
In this paper we study the following problem. There are n pages which clients can...
An approximation algorithm for the fault tolerant metric facility location problem
An approximation algorithm for the fault tolerant metric facility location problem
2003,
We consider a fault tolerant version of the metric facility location problem in which...
Primal–dual algorithms for connected facility location problems
Primal–dual algorithms for connected facility location problems
2004,
We consider the Connected Facility Location problem. We are given a graph G = (...
The power of priority algorithms for facility location and set cover
The power of priority algorithms for facility location and set cover
2004,
We apply and extend the priority algorithm framework introduced by Borodin, Nielsen,...
The data broadcast problem with non-uniform transmission times
The data broadcast problem with non-uniform transmission times
2003,
The Data Broadcast Problem consists of finding an infinite schedule to broadcast a...
A distributed ant algorithm for efficiently patrolling a network
A distributed ant algorithm for efficiently patrolling a network
2003,
We consider the problem of patrolling, i.e. ongoing exploration of a network by a...
An approximation algorithm for a large-scale facility location problem
An approximation algorithm for a large-scale facility location problem
2003,
We developed a new practical optimization method that gives approximate solutions for...
Finding a region with the minimum total L-1 distance from prescribed terminals
Finding a region with the minimum total L-1 distance from prescribed terminals
2003,
Given k terminals and n axis-parallel rectangular obstacles on the plane, algorithm...
A heuristic for Dijkstra's algorithm with many targets and its use in weighted matching algorithms
A heuristic for Dijkstra's algorithm with many targets and its use in weighted matching algorithms
2003,
We consider the single-source many-targets shortest-path (SSMTSP) problem in directed...
Papers per page: