Abstract:
We study combinatorial optimization problems related to covering and scheduling problems, such as the Minimum Hitting Set of Bundles problem, the Generalized Min Sum Set Cover problem, problems related to Matroid Intersection Covers, and the Bipartite Flow Scheduling problem. We present combinatorial approximation algorithms, study the computational complexity, and present polynomial-time algorithms for certain classes of instances.