Algorithms for capacitated rectangle stabbing and lot sizing with joint set-up costs

ABSTRACT

In the rectangle stabbing problem, we are given a set of axis parallel rectangles and a set of horizontal and vertical lines, and our goal is to find a minimum size subset of lines that intersect all the rectangles. In this article, we study the capacitated version of this problem in which the input includes an integral capacity for each line. The capacity of a line bounds the number of rectangles that the line can cover. We consider two versions of this problem. In the first, one is allowed to use only a single copy of each line (hard capacities), and in the second, one is allowed to use multiple copies of every line, but the multiplicities are counted in the size (or weight) of the solution (soft capacities).

We present an exact polynomial-time algorithm for the weighted one dimensional case with hard capacities that can be extended to the one dimensional weighted case with soft capacities. This algorithm is also extended to solve a certain capacitated multi-item lot-sizing inventory problem with joint set-up costs. For the case of d-dimensional rectangle stabbing with soft capacities, we present a 3d-approximation algorithm for the unweighted case. For d-dimensional rectangle stabbing problem with hard capacities, we present a bi-criteria algorithm that computes 4d-approximate solutions that use at most two copies of every line. Finally, we present hardness results for rectangle stabbing when the dimension is part of the input and for a two-dimensional weighted version with hard capacities.

REFERENCES

• 1: Shoshana Anily , Michal Tzur, Shipping Multiple Items by Capacitated Vehicles: An Optimal Dynamic Programming Approach, Transportation Science, v.39 n.2, p.233-248, May 2005 [doi>10.1287/trsc.1030.0080]
• 2: Anily, S., Tzur, M., and Wolsey, L. A. 2005. Multi-item lot-sizing with joint set-up cost. Submitted for publication.
• 3: Philippe Baptiste, Scheduling unit tasks to minimize the number of idle periods: a polynomial time algorithm for offline dynamic power management, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.364-367, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109598]
• 4: Judit Bar-Ilan , Guy Kortsarz , David Peleg, Generalized submodular cover problems and applications, Theoretical Computer Science, v.250 n.1-2, p.179-200, Jan 6, 2001 [doi>10.1016/S0304-3975(99)00130-9]
• 5: Julia Chuzhoy, Covering Problems with Hard Capacities, SIAM Journal on Computing, v.36 n.2, p.498-515, 2006 [doi>10.1137/S0097539703422479]
• 6: Even, G., Rawitz, D., and Shahar, S. 2006. Approximation algorithms for capacitated rectangle stabbing. In Proceedings of the 6th International Conference on Algorithms and Complexity. Lecture Notes in Computer Science, vol. 3998. Springer-Verlag, New York, 18--29.
• 7: Uriel Feige, A threshold of ln n for approximating set cover, Journal of the ACM (JACM), v.45 n.4, p.634-652, July 1998 [doi>10.1145/285055.285059]
• 8: Florian, M., Lenstra, J. K., and Rinooy Kan, A. H. G. 1980. Deterministic production planning: Algorithms and complexity. Manage. Sci. 26, 669--679.
• 9: Gandhi, R., Halperin, E., Khuller, S., Kortsarz, G., and Srinivasan, A. 2006. An improved approximation algorithm for vertex cover with hard capacities. J. Comput. Syst. Sci. 72, 1, 16--33.
• 10: Daya Ram Gaur , Toshihide Ibaraki , Ramesh Krishnamurti, Constant ratio approximation algorithms for the rectangle stabbing problem and the rectilinear partitioning problem, Journal of Algorithms, v.43 n.1, p.138-152, April 2002 [doi>10.1006/jagm.2002.1221]
• 11: Martin Charles Golumbic, Algorithmic Graph Theory and Perfect Graphs (Annals of Discrete Mathematics, Vol 57), North-Holland Publishing Co., Amsterdam, The Netherlands, 2004
• 12: Sudipto Guha , Refael Hassin , Samir Khuller , Einat Or, Capacitated vertex covering, Journal of Algorithms, v.48 n.1, p.257-270, August 2003 [doi>10.1016/S0196-6774(03)00053-1]
• 13: Refael Hassin , Nimrod Megiddo, Approximation algorithms for hitting objects with straight lines, Discrete Applied Mathematics, v.30 n.1, p.29-42, Jan. 7, 1991 [doi>10.1016/0166-218X(91)90011-K]
• 14: Kovaleva, S., and Spieksma, F. C. R. 2004. Approximation of rectangle stabbing and interval stabbing problems. In Proceedings of the 12th European Symposium on Algorithms. Lecture Notes in Computer Science, vol. 3221. Springer-Verlag, New York, 426--435.
• 15: Lawler, E. 2001. Combinatorial Optimization: Networks and matroids. Courier Dover Publications.
• 16: Levi, R., Lodi, A., and Sviridenko, M. 2007. Approximation algorithms for the multi-item capacitated lot-sizing problem via flow-cover inequalities. In Proceedings of the 12th Conference on Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science, vol. 4513. Springer-Verlag, New York, 454--468.
• 17: Ran Raz , Shmuel Safra, A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.475-484, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258641]
• 18: Shahar, S. 2006. Approximation algorithms for problems with geometrical structure. Ph.D. dissertation. School of Electrical Engineering, Tel-Aviv University, Tel-Aviv, Israel.
• 19: Wolsey, L. A. 1982. An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica 2, 385--393.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms, Theory

Keywords:
Approximation algorithms, capacitated covering, lot sizing, rectangle stabbing