Inapproximability of hypergraph vertex cover and applications to scheduling problems

Nikhil Bansal; Subhash Khot

doi:10.1007/978-3-642-14165-2_22

Inapproximability of hypergraph vertex cover and applications to scheduling problems

Nikhil Bansal, Subhash Khot

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Assuming the Unique Games Conjecture (UGC), we show optimal inapproximability results for two classic scheduling problems. We obtain a hardness of 2-ε for the problem of minimizing the total weighted completion time in concurrent open shops. We also obtain a hardness of 2-ε for minimizing the makespan in the assembly line problem. These results follow from a new inapproximability result for the Vertex Cover problem on k-uniform hypergraphs that is stronger and simpler than previous results. We show that assuming the UGC, for every k≥2, the problem is inapproximable within k-ε even when the hypergraph is almost k -partite.

Original language	English (US)
Title of host publication	Automata, Languages and Programming - 37th International Colloquium, ICALP 2010, Proceedings
Pages	250-261
Number of pages	12
Edition	PART 1
DOIs	https://doi.org/10.1007/978-3-642-14165-2_22
State	Published - 2010
Event	37th International Colloquium on Automata, Languages and Programming, ICALP 2010 - Bordeaux, France Duration: Jul 6 2010 → Jul 10 2010

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Number	PART 1
Volume	6198 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	37th International Colloquium on Automata, Languages and Programming, ICALP 2010
Country/Territory	France
City	Bordeaux
Period	7/6/10 → 7/10/10

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-14165-2_22

Cite this

Bansal, N., & Khot, S. (2010). Inapproximability of hypergraph vertex cover and applications to scheduling problems. In Automata, Languages and Programming - 37th International Colloquium, ICALP 2010, Proceedings (PART 1 ed., pp. 250-261). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6198 LNCS, No. PART 1). https://doi.org/10.1007/978-3-642-14165-2_22

Inapproximability of hypergraph vertex cover and applications to scheduling problems. / Bansal, Nikhil; Khot, Subhash.
Automata, Languages and Programming - 37th International Colloquium, ICALP 2010, Proceedings. PART 1. ed. 2010. p. 250-261 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6198 LNCS, No. PART 1).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Bansal, N & Khot, S 2010, Inapproximability of hypergraph vertex cover and applications to scheduling problems. in Automata, Languages and Programming - 37th International Colloquium, ICALP 2010, Proceedings. PART 1 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 1, vol. 6198 LNCS, pp. 250-261, 37th International Colloquium on Automata, Languages and Programming, ICALP 2010, Bordeaux, France, 7/6/10. https://doi.org/10.1007/978-3-642-14165-2_22

Bansal N, Khot S. Inapproximability of hypergraph vertex cover and applications to scheduling problems. In Automata, Languages and Programming - 37th International Colloquium, ICALP 2010, Proceedings. PART 1 ed. 2010. p. 250-261. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1). doi: 10.1007/978-3-642-14165-2_22

Bansal, Nikhil ; Khot, Subhash. / Inapproximability of hypergraph vertex cover and applications to scheduling problems. Automata, Languages and Programming - 37th International Colloquium, ICALP 2010, Proceedings. PART 1. ed. 2010. pp. 250-261 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1).

@inproceedings{3d0eca2c1a8543bea2d23111034807c8,

title = "Inapproximability of hypergraph vertex cover and applications to scheduling problems",

abstract = "Assuming the Unique Games Conjecture (UGC), we show optimal inapproximability results for two classic scheduling problems. We obtain a hardness of 2-ε for the problem of minimizing the total weighted completion time in concurrent open shops. We also obtain a hardness of 2-ε for minimizing the makespan in the assembly line problem. These results follow from a new inapproximability result for the Vertex Cover problem on k-uniform hypergraphs that is stronger and simpler than previous results. We show that assuming the UGC, for every k≥2, the problem is inapproximable within k-ε even when the hypergraph is almost k -partite.",

author = "Nikhil Bansal and Subhash Khot",

year = "2010",

doi = "10.1007/978-3-642-14165-2_22",

language = "English (US)",

isbn = "3642141641",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

number = "PART 1",

pages = "250--261",

booktitle = "Automata, Languages and Programming - 37th International Colloquium, ICALP 2010, Proceedings",

edition = "PART 1",

note = "37th International Colloquium on Automata, Languages and Programming, ICALP 2010 ; Conference date: 06-07-2010 Through 10-07-2010",

}

TY - GEN

T1 - Inapproximability of hypergraph vertex cover and applications to scheduling problems

AU - Bansal, Nikhil

AU - Khot, Subhash

PY - 2010

Y1 - 2010

N2 - Assuming the Unique Games Conjecture (UGC), we show optimal inapproximability results for two classic scheduling problems. We obtain a hardness of 2-ε for the problem of minimizing the total weighted completion time in concurrent open shops. We also obtain a hardness of 2-ε for minimizing the makespan in the assembly line problem. These results follow from a new inapproximability result for the Vertex Cover problem on k-uniform hypergraphs that is stronger and simpler than previous results. We show that assuming the UGC, for every k≥2, the problem is inapproximable within k-ε even when the hypergraph is almost k -partite.

AB - Assuming the Unique Games Conjecture (UGC), we show optimal inapproximability results for two classic scheduling problems. We obtain a hardness of 2-ε for the problem of minimizing the total weighted completion time in concurrent open shops. We also obtain a hardness of 2-ε for minimizing the makespan in the assembly line problem. These results follow from a new inapproximability result for the Vertex Cover problem on k-uniform hypergraphs that is stronger and simpler than previous results. We show that assuming the UGC, for every k≥2, the problem is inapproximable within k-ε even when the hypergraph is almost k -partite.

UR - http://www.scopus.com/inward/record.url?scp=77955327992&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77955327992&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-14165-2_22

DO - 10.1007/978-3-642-14165-2_22

M3 - Conference contribution

AN - SCOPUS:77955327992

SN - 3642141641

SN - 9783642141645

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 250

EP - 261

BT - Automata, Languages and Programming - 37th International Colloquium, ICALP 2010, Proceedings

T2 - 37th International Colloquium on Automata, Languages and Programming, ICALP 2010

Y2 - 6 July 2010 through 10 July 2010

ER -

Inapproximability of hypergraph vertex cover and applications to scheduling problems

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this