A lower bound for the hitting set size for combinatorial rectangles and an application

DOI10.1016/S0020-0190(02)00475-1zbMath1156.05302OpenAlexW1972544244MaRDI QIDQ1007576

L. Sunil Chandran

Publication date: 23 March 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(02)00475-1

zbMATH Keywords

combinatorial problemshitting setcombinatorial rectangle

Mathematics Subject Classification ID

Approximation algorithms (68W25) Randomized algorithms (68W20) Combinatorial aspects of packing and covering (05B40)

Related Items (2)

Recursive methods for some problems in coding and random permutations ⋮ On combinatorial rectangles with minimum ∞−discrepancy

Cites Work

• Efficient construction of a small hitting set for combinatorial rectangles in high dimension
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation

This page was built for publication: A lower bound for the hitting set size for combinatorial rectangles and an application