Recoverable Values for Independent Sets (Q3012827): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||||||||||||||
(8 intermediate revisions by 6 users not shown) | |||||||||||||||
aliases / en / 0 | aliases / en / 0 | ||||||||||||||
Recoverable values for independent sets | |||||||||||||||
description / en | description / en | ||||||||||||||
scientific article | scientific article; zbMATH DE number 6406611 | ||||||||||||||
Property / author | |||||||||||||||
Property / author: Uriel Feige / rank | |||||||||||||||
Property / title | |||||||||||||||
Recoverable values for independent sets (English) | |||||||||||||||
Property / title: Recoverable values for independent sets (English) / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / zbMATH Open document ID | |||||||||||||||
Property / zbMATH Open document ID: 1307.05174 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / DOI | |||||||||||||||
Property / DOI: 10.1002/rsa.20492 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / author | |||||||||||||||
Property / author: Uriel Feige / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / published in | |||||||||||||||
Property / published in: Random Structures & Algorithms / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / publication date | |||||||||||||||
20 February 2015
| |||||||||||||||
Property / publication date: 20 February 2015 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / Mathematics Subject Classification ID | |||||||||||||||
Property / Mathematics Subject Classification ID: 05C85 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / Mathematics Subject Classification ID | |||||||||||||||
Property / Mathematics Subject Classification ID: 05C07 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / Mathematics Subject Classification ID | |||||||||||||||
Property / Mathematics Subject Classification ID: 68T20 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / Mathematics Subject Classification ID | |||||||||||||||
Property / Mathematics Subject Classification ID: 90B80 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / zbMATH DE Number | |||||||||||||||
Property / zbMATH DE Number: 6406611 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / MaRDI profile type | |||||||||||||||
Property / MaRDI profile type: MaRDI publication profile / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / OpenAlex ID | |||||||||||||||
Property / OpenAlex ID: W2057440575 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / OpenAlex ID | |||||||||||||||
Property / OpenAlex ID: W2568310503 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / arXiv ID | |||||||||||||||
Property / arXiv ID: 1103.5609 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / zbMATH Keywords | |||||||||||||||
independent set | |||||||||||||||
Property / zbMATH Keywords: independent set / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / zbMATH Keywords | |||||||||||||||
approximation algorithms | |||||||||||||||
Property / zbMATH Keywords: approximation algorithms / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / zbMATH Keywords | |||||||||||||||
heuristics | |||||||||||||||
Property / zbMATH Keywords: heuristics / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Q3002828 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: On approximation properties of the independent set problem for low degree graphs / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Structural Information and Communication Complexity / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: PASS approximation: a framework for analyzing and designing heuristics / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Recoverable Values for Independent Sets / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Lower bounds on the independence number in terms of the degrees / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Q5365143 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: On the Inapproximability of Vertex Cover on k-Partite k-Uniform Hypergraphs / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Approximations of Weighted Independent Set and Hereditary Subset Problems / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Greed is good: Approximating independent sets in sparse and bounded-degree graphs / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Clique is hard to approximate within \(n^{1-\epsilon}\) / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Efficient bounds for the stable set, vertex cover and set packing problems / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Vertex cover might be hard to approximate to within \(2 - \varepsilon \) / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Vertex packings: Structural properties and algorithms / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: A note on greedy algorithms for the maximum weighted independent set problem / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Large induced degenerate subgraphs / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: New bounds for contagious sets / rank | |||||||||||||||
Normal rank |
Latest revision as of 18:00, 9 July 2024
scientific article; zbMATH DE number 6406611
- Recoverable values for independent sets
Language | Label | Description | Also known as |
---|---|---|---|
English | Recoverable Values for Independent Sets |
scientific article; zbMATH DE number 6406611 |
|
Statements
Recoverable Values for Independent Sets (English)
0 references
Recoverable values for independent sets (English)
0 references
6 July 2011
0 references
20 February 2015
0 references
independent set
0 references
approximation algorithms
0 references
heuristics
0 references