Journal: Algorithmica

Found 758 papers in total
Approximation Algorithms for k‐hurdle Problems
Approximation Algorithms for k‐hurdle Problems
2011,
The polynomial‐time solvable k ‐hurdle problem is a natural...
Stochastic models for budget optimization in search-based advertising
Stochastic models for budget optimization in search-based advertising
2010,
Internet search companies sell advertisement slots based on users' search queries via...
A sequential algorithm for generating random graphs
A sequential algorithm for generating random graphs
2010,
We present a nearly-linear time algorithm for counting and randomly generating simple...
Multi-color pebble motion on graphs
Multi-color pebble motion on graphs
2010,
We consider a graph with n vertices, and p < n pebbles of m colors. A pebble move...
The 1-fixed endpoint path cover problem is polynomial on interval graphs
The 1-fixed endpoint path cover problem is polynomial on interval graphs
2010,
We consider a variant of the path cover problem, namely, the k -fixed-endpoint path...
Guarding a terrain by two watchtowers
Guarding a terrain by two watchtowers
2010,
Given a polyhedral terrain T with n vertices, the two-watchtower problem for T asks to...
Approximation algorithms for scheduling with reservations
Approximation algorithms for scheduling with reservations
2010,
We study the problem of non-preemptively scheduling n independent sequential jobs on a...
Absolute and asymptotic bounds for online frequency allocation in cellular networks
Absolute and asymptotic bounds for online frequency allocation in cellular networks
2010,
Given a cellular (mobile telephone) network, whose geographical coverage area is...
The stable roommates problem with choice functions
The stable roommates problem with choice functions
2010,
The stable marriage theorem of Gale and Shapley states that for n men and n women...
An efficient algorithm for batch stability testing
An efficient algorithm for batch stability testing
2010,
Given a stable marriage problem instance represented by a bipartite graph having 2 n...
Parameterized complexity and local search approaches for the stable marriage problem with ties
Parameterized complexity and local search approaches for the stable marriage problem with ties
2010,
We consider the variant of the classical Stable Marriage problem where preference...
Housing markets through graphs
Housing markets through graphs
2010,
Housing market is a special type of exchange economy where each agent is endowed with...
Almost stable matchings by truncating the Gale–Shapley algorithm
Almost stable matchings by truncating the Gale–Shapley algorithm
2010,
We show that the ratio of matched individuals to blocking pairs grows linearly with...
Circular stable matching and 3-way kidney transplant
Circular stable matching and 3-way kidney transplant
2010,
We consider the following version of the stable matching problem. Suppose that men...
Cheating strategies for the Gale-Shapley algorithm with complete preference lists
Cheating strategies for the Gale-Shapley algorithm with complete preference lists
2010,
This paper deals with a strategic issue in the stable marriage model with complete...
Assigning papers to referees
Assigning papers to referees
2010,
Refereed conferences require every submission to be reviewed by members of a program...
A polynomial-time algorithm to find von Neumann-Morgenstern stable matchings in marriage games
A polynomial-time algorithm to find von Neumann-Morgenstern stable matchings in marriage games
2010,
This paper considers von Neumann-Morgenstern (vNM) stable sets in marriage games....
Faster algorithms for stable allocation problems
Faster algorithms for stable allocation problems
2010,
We consider a high-multiplicity generalization of the classical stable matching...
A preemptive algorithm for maximizing disjoint paths on trees
A preemptive algorithm for maximizing disjoint paths on trees
2010,
We consider the on-line version of the maximum vertex disjoint path problem when the...
Kinetic facility location
Kinetic facility location
2010,
We present a deterministic kinetic data structure for the facility location problem...
Improved bounds for wireless localization
Improved bounds for wireless localization
2010,
We consider a novel class of art gallery problems inspired by wireless localization...
Continuous lunches are free plus the design of optimal optimization algorithms
Continuous lunches are free plus the design of optimal optimization algorithms
2010,
This paper analyses extensions of No-Free-Lunch (NFL) theorems to countably infinite...
Note on the structure of Kruskal's algorithm
Note on the structure of Kruskal's algorithm
2010,
We study the merging process when Kruskal's algorithm is run with random graphs as...
Largest and smallest convex hulls for imprecise points
Largest and smallest convex hulls for imprecise points
2010,
Assume that a set of imprecise points is given, where each point is specified by a...
Papers per page: