Maximum-Weight Independent Set is as "Well-Approximated" as the Unweighted One.

We devise an approximation-preserving reduction of expansion O between weighted and unweighted versions of a class of problems called weighted hereditary induced-subgraph maximisation problems. This allows us to perform a first improvement of the best approximation ratio for the weighted independent set problem.

MoreLess

Year of publication:	1999
Authors:	Demange, M. ; Paschos, V.T.
Institutions:	Centre de recherche de mathématiques et économie mathématique (CERMSEM), Centre d'Économie de la Sorbonne
Subject:	MATHEMATICAL ANALYSIS \| PROBABILITY \| WEIGHT

More details

Series:	Papiers d'Economie Mathématique et Applications.
Type of publication:	Book / Working Paper
Notes:	18 pages
Classification:	C51 - Model Construction and Estimation ; I12 - Health Production: Nutrition, Mortality, Morbidity, Substance Abuse and Addiction, Disability, and Economic Behavior
Source:	RePEc - Research Papers in Economics

Persistent link: https://ebvufind01.dmz1.zbw.eu/10005630673