NDLI: Maximum Weight Partial Colorings on Sparse Random Graphs

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Jaslar, Steven Tatikonda, Sekhar
Copyright Year	2011
Abstract	We examine the asymptotic behavior of optimal values and optimal configurations for the maximum weight partial coloring (MWPC) problem on sparse random graphs. The MWPC problem is a weighted version of the partial coloring problem, and it is a generalization of the maximum weight independent set (MWIS) problem. The MWPC problem is an illustrative example of how to employ the local weak convergence method on combinatorial optimization problems that are defined via a graphical model and have a nonbinary alphabet. Many of the results are inspired by Gamarnik, Nowicki, and Swirscsz Random Structures Algorithms, 28 (2005), pp.76106. They showed that if vertex weights were sampled independently from a nonatomic distribution and if a particular fixed point equation had a unique solution, then the scaled MWIS value on sparse ErdsRnyi graphs converges in probability. Under the same conditions, Sanghavi and Shah http://arxiv.org/pdf/cs/0508097v2 (12 April 2008) showed how the max-product message passing algorithm can be used to produce 1+ε approximations with probability 1-ε. There are major difficulties in applying the above techniques to other natural combinatorial optimization problems. We show how to strengthen them so that they can be applied to a new range of problems which includes the MWPC problem. In the MWPC case, we show how our techniques can be used to get new convergence results on sparse ErdsRnyi graphseven in the case where the weights are sampled from a discrete distribution. This depends on new results on how certain long range independence properties occur almost surely for branching processes.
Starting Page	934
Ending Page	955
Page Count	22
File Format	PDF
ISSN	08954801
DOI	10.1137/090755771
e-ISSN	10957146
Journal	SIAM Journal on Discrete Mathematics (SJDMEC)
Issue Number	2
Volume Number	25
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2011-07-01
Access Restriction	Subscribed
Subject Keyword	Random graphs branching process ErdsRnyi graphs colorings partial colorings Combinatorial probability random graphs Dynamic programming Central limit and other weak theorems Coloring of graphs and hypergraphs
Content Type	Text
Resource Type	Article
Subject	Mathematics

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

Limit Theorems for Monochromatic Stars

Universal Limit Theorems in Graph Coloring Problems With Connections to Extremal Combinatorics

Central limit theorems for combinatorial optimization problems on sparse Erd\H{o}s-R\'enyi graphs

A fourth moment phenomenon for asymptotic normality of monochromatic subgraphs

Susceptibility in subcritical random graphs

A note on the independence number, domination number and related parameters of random binary search trees and random recursive trees

Inhomogeneous random graphs, isolated vertices, and Poisson approximation

Limit theorems for exponential random graphs

A new random mapping model

Maximum Weight Partial Colorings on Sparse Random Graphs

Similar Documents

Limit Theorems for Monochromatic Stars

Universal Limit Theorems in Graph Coloring Problems With Connections to Extremal Combinatorics

Central limit theorems for combinatorial optimization problems on sparse Erd\H{o}s-R\'enyi graphs

A fourth moment phenomenon for asymptotic normality of monochromatic subgraphs

Susceptibility in subcritical random graphs

A note on the independence number, domination number and related parameters of random binary search trees and random recursive trees

Inhomogeneous random graphs, isolated vertices, and Poisson approximation

Limit theorems for exponential random graphs

A new random mapping model

Maximum Weight Partial Colorings on Sparse Random Graphs