Journal: Algorithmica

Found 758 papers in total
Combinatorial algorithms for data migration to minimize average completion time
Combinatorial algorithms for data migration to minimize average completion time
2009,
The data migration problem is to compute an efficient plan for moving data stored on...
Weighted sum coloring in batch scheduling of conflicting jobs
Weighted sum coloring in batch scheduling of conflicting jobs
2009,
Motivated by applications in batch scheduling of jobs in manufacturing systems and...
Approximation algorithms for multi-criteria traveling salesman problems
Approximation algorithms for multi-criteria traveling salesman problems
2009,
We analyze approximation algorithms for several variants of the traveling salesman...
Stackelberg strategies for selfish routing in general multicommodity networks
Stackelberg strategies for selfish routing in general multicommodity networks
2009,
A natural generalization of the selfish routing setting arises when some of the users...
Labeling schemes for tree representation
Labeling schemes for tree representation
2009,
This paper deals with compact label-based representations for trees. Consider an n...
Scheduling Techniques for Media-on-Demand
Scheduling Techniques for Media-on-Demand
2008,
Broadcasting popular media to clients is the ultimate scalable solution for...
Bandwidth-Constrained Allocation in Grid Computing
Bandwidth-Constrained Allocation in Grid Computing
2008,
Grid computing systems pool together the resources of many workstations to create a...
Incremental medians via online bidding
Incremental medians via online bidding
2008,
In the k -median problem we are given sets of facilities and customers, and distances...
All-pairs shortest paths with real weights in O(n3/log n) time
All-pairs shortest paths with real weights in O(n3/log n) time
2008,
We describe an O(n 3 /log n) -time algorithm for the all-pairs-shortest-paths problem...
On the competitive ratio for online facility location
On the competitive ratio for online facility location
2008,
We consider the problem of Online Facility Location, where the demand points arrive...
Generalization of Earliest-Deadline-First (EDF) and the Least-Laxity-First (LLF): Identifying all optimal online algorithms for minimizing maximum lateness
Generalization of Earliest-Deadline-First (EDF) and the Least-Laxity-First (LLF): Identifying all optimal online algorithms for minimizing maximum lateness
2008,
It is well known that the Earliest-Deadline-First and the Least-Laxity-First...
Simple stochastic games, parity games, mean payoff games and discounted payoff games are all LP-type problems
Simple stochastic games, parity games, mean payoff games and discounted payoff games are all LP-type problems
2007,
We show that a Simple Stochastic Game (SSG) can be formulated as an LP-type problem....
A fully polynomial time approximation scheme for Quickest Multicommodity Flows with Inflow-Dependent Transit Times
A fully polynomial time approximation scheme for Quickest Multicommodity Flows with Inflow-Dependent Transit Times
2007,
Given a network with capacities and transit times on the arcs, the quickest flow...
Minimizing total flow time and total completion time with immediate dispatching
Minimizing total flow time and total completion time with immediate dispatching
2007,
We consider the problem of scheduling jobs arriving over time in a multiprocessor...
Real-time scheduling with a budget
Real-time scheduling with a budget
2007,
Suppose that we are given a set of jobs, where each job has a processing time, a...
Maximizing the total profit of rectangles packed into a rectangle
Maximizing the total profit of rectangles packed into a rectangle
2007,
We consider the following rectangle packing problem. Given a set of rectangles, each...
Selfish load balancing and atomic congestion games
Selfish load balancing and atomic congestion games
2007,
We revisit a classical load balancing problem in the modern context of decentralized...
Approximation algorithms for the unsplittable flow problem
Approximation algorithms for the unsplittable flow problem
2007,
We present approximation algorithms for the unsplittable flow problem (UFP) in...
Multicriteria global minimum cuts
Multicriteria global minimum cuts
2006,
We consider two multicriteria versions of the global minimum cut problem in undirected...
The Freeze-Tag Problem: How to wake up a swarm of robots
The Freeze-Tag Problem: How to wake up a swarm of robots
2006,
An optimization problem that naturally arises in the study of swarm robotics is the...
A slightly improved sub-cubic algorithm for the all pairs shortest paths problem with real edge lengths
A slightly improved sub-cubic algorithm for the all pairs shortest paths problem with real edge lengths
2006,
We present an O(n 3 √(log log n)/logn) -time algorithm for the All Pairs...
Deterministic rendezvous in graphs
Deterministic rendezvous in graphs
2006,
Two mobile agents having distinct identifiers and located in nodes of an unknown...
An experimental study of random knapsack problems
An experimental study of random knapsack problems
2006,
The size of the Pareto curve for the bicriteria version of the knapsack problem is...
General perfectly periodic scheduling
General perfectly periodic scheduling
2006,
In a perfectly periodic schedule, each job must be scheduled precisely every some...
Papers per page: