NDLI: Models and heuristic algorithms for a weighted vertex coloring problem

Content Provider	Springer Nature Link
Author	Malaguti, Enrico Monaci, Michele Toth, Paolo
Copyright Year	2008
Abstract	We consider a weighted version of the well-known Vertex Coloring Problem (VCP) in which each vertex i of a graph G has associated a positive weight w i . Like in VCP, one is required to assign a color to each vertex in such a way that colors on adjacent vertices are different, and the objective is to minimize the sum of the costs of the colors used. While in VCP the cost of each color is equal to one, in the Weighted Vertex Coloring Problem (WVCP) the cost of each color depends on the weights of the vertices assigned to that color, and it equals the maximum of these weights. WVCP is known to be NP-hard and arises in practical scheduling applications, where it is also known as Scheduling on a Batch Machine with Job Compatibilities. We propose three alternative Integer Linear Programming (ILP) formulations for WVCP: one is used to derive, dropping integrality requirement for the variables, a tight lower bound on the solution value, while a second one is used to derive a 2-phase heuristic algorithm, also embedding fast refinement procedures aimed at improving the quality of the solutions found. Computational results on a large set of instances from the literature are reported.
Starting Page	503
Ending Page	526
Page Count	24
File Format	PDF
ISSN	13811231
Journal	Journal of Heuristics
Volume Number	15
Issue Number	5
e-ISSN	15729397
Language	English
Publisher	Springer US
Publisher Date	2008-05-28
Publisher Place	Boston
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Mathematical models Vertex coloring Traffic matrix decomposition Computational experiments Calculus of Variations and Optimal Control; Optimization Artificial Intelligence (incl. Robotics) Operations Research/Decision Theory Operations Research, Mathematical Programming
Content Type	Text
Resource Type	Article
Subject	Control and Optimization Artificial Intelligence Management Science and Operations Research Computer Networks and Communications Information Systems Software

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

A Range-Compaction Heuristic for Graph Coloring

A decomposition heuristics for the container ship stowage problem

Approximating the maximum vertex/edge weighted clique using local search

A hybrid heuristic for the maximum clique problem

A comparison of problem decomposition techniques for the FAP

New Results on the Queens_n 2 Graph Coloring Problem

Heuristic Solution Methods for the Multilevel Generalized Assignment Problem

An Iterative Construction Heuristic for the Ore Selection Problem

A Hybrid Heuristic for the p-Median Problem

Models and heuristic algorithms for a weighted vertex coloring problem

Similar Documents

A Range-Compaction Heuristic for Graph Coloring

A decomposition heuristics for the container ship stowage problem

Approximating the maximum vertex/edge weighted clique using local search

A hybrid heuristic for the maximum clique problem

A comparison of problem decomposition techniques for the FAP

New Results on the Queens_n 2 Graph Coloring Problem

Heuristic Solution Methods for the Multilevel Generalized Assignment Problem

An Iterative Construction Heuristic for the Ore Selection Problem

A Hybrid Heuristic for the p-Median Problem

Models and heuristic algorithms for a weighted vertex coloring problem