Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem
- 1 April 2002
- journal article
- Published by Elsevier in Journal of Algorithms
- Vol. 43 (1) , 138-152
- https://doi.org/10.1006/jagm.2002.1221
Abstract
No abstract availableFunding Information
- Natural Sciences and Engineering Research Council of Canada
- Ministry of Education, Culture, Sports, Science and Technology
This publication has 11 references indexed in Scilit:
- Approximation algorithms for combinatorial problemsPublished by Elsevier ,2007
- Approximations for the general block distribution of a matrixPublished by Springer Nature ,1998
- Rectilinear Partitioning of Irregular Data Parallel ComputationsJournal of Parallel and Distributed Computing, 1994
- On the hardness of approximating minimization problemsJournal of the ACM, 1994
- Improved algorithms for mapping pipelined and parallel computationsIEEE Transactions on Computers, 1991
- Approximation algorithms for hitting objects with straight linesDiscrete Applied Mathematics, 1991
- Partitioning problems in parallel, pipeline, and distributed computingIEEE Transactions on Computers, 1988
- A Partitioning Strategy for Nonuniform Problems on MultiprocessorsIEEE Transactions on Computers, 1987
- Approximation Algorithms for the Set Covering and Vertex Cover ProblemsSIAM Journal on Computing, 1982
- A Greedy Heuristic for the Set-Covering ProblemMathematics of Operations Research, 1979