NDLI: Vertex Cover Meets Scheduling

Content Provider	Springer Nature Link
Author	Epstein, Leah Levin, Asaf Woeginger, Gerhard J.
Copyright Year	2015
Abstract	We consider a hybrid two-stage optimization problem that generalizes two classic combinatorial optimization problems: (i) weighted vertex cover in graphs, and (ii) makespan minimization in multiprocessor scheduling. An instance specifies a machine environment, a set of jobs, and an undirected graph over the jobs. The goal is to select a subset of the jobs that forms a vertex cover and to schedule it on a set of parallel machines so as to minimize the makespan. We call this problem family vertex cover meets multiprocessor scheduling (VCMS). The problem is motivated by networks where vertices represent servers and each edge corresponds to a task that can be done by any of the two servers of its endpoint. Each selected server can complete any number of tasks assigned to it within a given time defined by its weight, as the time consumption of the server is roughly equal to its activation time. The activation is performed by a set of $$m$$ processors, such that every selected server is activated by one processor, and the goal is to minimize the maximum total activation time assigned to any processor. We design a multitude of approximation algorithms for VCMS and its variants, many of which match or almost match the best approximation bound known for the vertex cover problem. In particular, we give a $$2$$ -approximation for the case of a fixed number of unrelated machines, a $$3$$ -approximation for an arbitrary number of unrelated machines, and a $$(2+\varepsilon )$$ -approximation for an arbitrary number of identical machines. Furthermore we consider special graph classes for which the weighted vertex cover problem can be solved to optimality in polynomial time: for many of these classes, there is a PTAS for VCMS on identical machines; for bipartite graphs, however, VCMS on identical machines turns out to be APX-hard. Finally, we study the bin packing counterpart of VCMS and design a $$(2+\varepsilon )$$ -approximation algorithm for it.
Starting Page	1148
Ending Page	1173
Page Count	26
File Format	PDF
ISSN	01784617
Journal	Algorithmica
Volume Number	74
Issue Number	3
e-ISSN	14320541
Language	English
Publisher	Springer US
Publisher Date	2015-03-28
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Algorithm Analysis and Problem Complexity Theory of Computation Mathematics of Computing Algorithms Computer Systems Organization and Communication Networks Data Structures, Cryptology and Information Theory
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Single Machine Precedence Constrained Scheduling Is a Vertex Cover Problem

Stackelberg Bipartite Vertex Cover and the Preflow Algorithm

On Cutwidth Parameterized by Vertex Cover

Fixed-Parameter Evolutionary Algorithms and the Vertex Cover Problem

A Primal-Dual Approximation Algorithm for Partial Vertex Cover: Making Educated Guesses

Small Vertex Cover makes Petri Net Coverability and Boundedness Easier

Planar Feedback Vertex Set and Face Cover: Combinatorial Bounds and Subexponential Algorithms

The Complexity of König Subgraph Problems and Above-Guarantee Vertex Cover

Scheduling Independent Multiprocessor Tasks

Vertex Cover Meets Scheduling

Similar Documents

Single Machine Precedence Constrained Scheduling Is a Vertex Cover Problem

Stackelberg Bipartite Vertex Cover and the Preflow Algorithm

On Cutwidth Parameterized by Vertex Cover

Fixed-Parameter Evolutionary Algorithms and the Vertex Cover Problem

A Primal-Dual Approximation Algorithm for Partial Vertex Cover: Making Educated Guesses

Small Vertex Cover makes Petri Net Coverability and Boundedness Easier

Planar Feedback Vertex Set and Face Cover: Combinatorial Bounds and Subexponential Algorithms

The Complexity of König Subgraph Problems and Above-Guarantee Vertex Cover

Scheduling Independent Multiprocessor Tasks

Vertex Cover Meets Scheduling