Ontology type: schema:ScholarlyArticle
2007-10-13
AUTHORSSubhash Khot, Richard J. Lipton, Evangelos Markakis, Aranyak Mehta
ABSTRACTWe consider the following allocation problem arising in the setting of combinatorial auctions: a set of goods is to be allocated to a set of players so as to maximize the sum of the utilities of the players (i.e., the social welfare). In the case when the utility of each player is a monotone submodular function, we prove that there is no polynomial time approximation algorithm which approximates the maximum social welfare by a factor better than 1−1/e≃0.632, unless P=NP. Our result is based on a reduction from a multi-prover proof system for MAX-3-COLORING. More... »
PAGES3-18
http://scigraph.springernature.com/pub.10.1007/s00453-007-9105-7
DOIhttp://dx.doi.org/10.1007/s00453-007-9105-7
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1027463644
JSON-LD is the canonical representation for SciGraph data.
TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT
[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
"about": [
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/14",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Economics",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1402",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Applied Economics",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Georgia Institute of Technology, 30332, Atlanta, GA, USA",
"id": "http://www.grid.ac/institutes/grid.213917.f",
"name": [
"Georgia Institute of Technology, 30332, Atlanta, GA, USA"
],
"type": "Organization"
},
"familyName": "Khot",
"givenName": "Subhash",
"id": "sg:person.015757022753.38",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015757022753.38"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Telcordia Research, 07960, Morristown, NJ, USA",
"id": "http://www.grid.ac/institutes/None",
"name": [
"Georgia Institute of Technology, 30332, Atlanta, GA, USA",
"Telcordia Research, 07960, Morristown, NJ, USA"
],
"type": "Organization"
},
"familyName": "Lipton",
"givenName": "Richard J.",
"id": "sg:person.010133373171.27",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010133373171.27"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Dept. of Computer Science, University of Toronto, 10 King\u2019s College Road, M5S3G4, Toronto, ON, Canada",
"id": "http://www.grid.ac/institutes/grid.17063.33",
"name": [
"Dept. of Computer Science, University of Toronto, 10 King\u2019s College Road, M5S3G4, Toronto, ON, Canada"
],
"type": "Organization"
},
"familyName": "Markakis",
"givenName": "Evangelos",
"id": "sg:person.014013771241.29",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014013771241.29"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "IBM Almaden Research Center, 650 Harry Rd, 95120, San Jose, CA, USA",
"id": "http://www.grid.ac/institutes/grid.481551.c",
"name": [
"IBM Almaden Research Center, 650 Harry Rd, 95120, San Jose, CA, USA"
],
"type": "Organization"
},
"familyName": "Mehta",
"givenName": "Aranyak",
"id": "sg:person.010106546671.08",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010106546671.08"
],
"type": "Person"
}
],
"citation": [
{
"id": "sg:pub.10.1007/bf01202286",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1026973980",
"https://doi.org/10.1007/bf01202286"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-540-27810-8_4",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1019890075",
"https://doi.org/10.1007/978-3-540-27810-8_4"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/11600930_10",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1037677693",
"https://doi.org/10.1007/11600930_10"
],
"type": "CreativeWork"
}
],
"datePublished": "2007-10-13",
"datePublishedReg": "2007-10-13",
"description": "Abstract\nWe consider the following allocation problem arising in the setting of combinatorial auctions: a set of goods is to be allocated to a set of players so as to maximize the sum of the utilities of the players (i.e., the social welfare). In the case when the utility of each player is a monotone submodular function, we prove that there is no polynomial time approximation algorithm which approximates the maximum social welfare by a factor better than 1\u22121/e\u22430.632, unless P=NP. Our result is based on a reduction from a multi-prover proof system for MAX-3-COLORING.",
"genre": "article",
"id": "sg:pub.10.1007/s00453-007-9105-7",
"inLanguage": "en",
"isAccessibleForFree": false,
"isPartOf": [
{
"id": "sg:journal.1047644",
"issn": [
"0178-4617",
"1432-0541"
],
"name": "Algorithmica",
"publisher": "Springer Nature",
"type": "Periodical"
},
{
"issueNumber": "1",
"type": "PublicationIssue"
},
{
"type": "PublicationVolume",
"volumeNumber": "52"
}
],
"keywords": [
"combinatorial auctions",
"maximum social welfare",
"set of goods",
"set of players",
"submodular utility functions",
"social welfare",
"utility function",
"auctions",
"allocation problem",
"monotone submodular function",
"players",
"welfare",
"goods",
"utility",
"submodular functions",
"set",
"inapproximability results",
"results",
"sum",
"setting",
"factors",
"problem",
"cases",
"reduction",
"function",
"system",
"approximation algorithm",
"time approximation algorithm",
"algorithm",
"polynomial-time approximation algorithm",
"NPs",
"proof system"
],
"name": "Inapproximability Results for Combinatorial Auctions with Submodular Utility Functions",
"pagination": "3-18",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1027463644"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/s00453-007-9105-7"
]
}
],
"sameAs": [
"https://doi.org/10.1007/s00453-007-9105-7",
"https://app.dimensions.ai/details/publication/pub.1027463644"
],
"sdDataset": "articles",
"sdDatePublished": "2022-05-20T07:24",
"sdLicense": "https://scigraph.springernature.com/explorer/license/",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/article/article_432.jsonl",
"type": "ScholarlyArticle",
"url": "https://doi.org/10.1007/s00453-007-9105-7"
}
]Download the RDF metadata as: json-ld nt turtle xml License info
JSON-LD is a popular format for linked data which is fully compatible with JSON.
curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s00453-007-9105-7'
N-Triples is a line-based linked data format ideal for batch operations.
curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s00453-007-9105-7'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-007-9105-7'
RDF/XML is a standard XML format for linked data.
curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-007-9105-7'
This table displays all metadata directly associated to this object as RDF triples.
133 TRIPLES
22 PREDICATES
60 URIs
49 LITERALS
6 BLANK NODES