Ontology type: schema:MonetaryGrant

2012-2018

499988 USD

Combinatorial optimization problems are of great importance to numerous applications. They arise in operations research, machine learning, VLSI design, computational biology and many other areas. Many optimization problems however are NP-hard and thus cannot be solved exactly in polynomial time unless P=NP. It is natural therefore to look for approximation algorithms, efficient algorithms that find only approximate solutions. Design and analysis of approximation algorithms is a very active research area. Various approaches for solving combinatorial optimization problems have appeared in the last three decades. However, despite significant progress, many important problems are still open. This research project aims to advance the application of metric geometry techniques for solving combinatorial optimization problems, investigate new methods for designing approximation algorithms, and develop tools for analyzing the performance of approximation algorithms on real-life instances. This research project will be both theoretically important and practically relevant and it will lead to development of approximation algorithms for important applied problems that occur in many fields of science and engineering. Specifically, the PI will work on the following problems. * Traditionally most research has focused on analyzing the worst case performance of approximation algorithms. However, practitioners observe that instances of combinatorial optimization problems that arise in practice are often not as hard as worst case instances. The PI will study semi-random models for various combinatorial optimization problems, and develop approximation algorithms that perform well on semi-random instances. This can perhaps explain what we see in practice. * Recent research in the hardness of approximation initiated by Khot identified Unique Games Problem as a combinatorial obstacle to the development of approximation algorithms for many problems. The PI will study algorithmic techniques for solving the Unique Games Problem. * The PI will study lift-and-project hierarchies of linear programming (LP) and semi-definite programming (SDP) relaxations, analyze their integrality gaps, and design subexponential approximation algorithms that use these hierarchies. * There is a close connection between some areas of theoretical computer science and pure mathematics. To settle down some problems in combinatorial optimization, we need to resolve closely connected open problems in analysis. The PI will explore several problems with deep ties to computer science and mathematics. More... »

http://www.nsf.gov/awardsearch/showAward?AWD_ID=1150062&HistoricalAwards=false

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/2201",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/2201",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/2208",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"type": "DefinedTerm"
}
],
"amount": {
"currency": "USD",
"type": "MonetaryAmount",
"value": "499988"
},
"description": "Combinatorial optimization problems are of great importance to numerous applications. They arise in operations research, machine learning, VLSI design, computational biology and many other areas. Many optimization problems however are NP-hard and thus cannot be solved exactly in polynomial time unless P=NP. It is natural therefore to look for approximation algorithms, efficient algorithms that find only approximate solutions. Design and analysis of approximation algorithms is a very active research area. Various approaches for solving combinatorial optimization problems have appeared in the last three decades. However, despite significant progress, many important problems are still open. This research project aims to advance the application of metric geometry techniques for solving combinatorial optimization problems, investigate new methods for designing approximation algorithms, and develop tools for analyzing the performance of approximation algorithms on real-life instances. This research project will be both theoretically important and practically relevant and it will lead to development of approximation algorithms for important applied problems that occur in many fields of science and engineering. Specifically, the PI will work on the following problems. * Traditionally most research has focused on analyzing the worst case performance of approximation algorithms. However, practitioners observe that instances of combinatorial optimization problems that arise in practice are often not as hard as worst case instances. The PI will study semi-random models for various combinatorial optimization problems, and develop approximation algorithms that perform well on semi-random instances. This can perhaps explain what we see in practice. * Recent research in the hardness of approximation initiated by Khot identified Unique Games Problem as a combinatorial obstacle to the development of approximation algorithms for many problems. The PI will study algorithmic techniques for solving the Unique Games Problem. * The PI will study lift-and-project hierarchies of linear programming (LP) and semi-definite programming (SDP) relaxations, analyze their integrality gaps, and design subexponential approximation algorithms that use these hierarchies. * There is a close connection between some areas of theoretical computer science and pure mathematics. To settle down some problems in combinatorial optimization, we need to resolve closely connected open problems in analysis. The PI will explore several problems with deep ties to computer science and mathematics.",
"endDate": "2018-06-30T00:00:00Z",
"funder": {
"id": "https://www.grid.ac/institutes/grid.457785.c",
"type": "Organization"
},
"id": "sg:grant.3133011",
"identifier": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"3133011"
]
},
{
"name": "nsf_id",
"type": "PropertyValue",
"value": [
"1150062"
]
}
],
"inLanguage": [
"en"
],
"keywords": [
"development",
"worst case performance",
"career",
"active research area",
"VLSI design",
"deep ties",
"application",
"combinatorial obstacle",
"practitioners",
"random model",
"semi-random instances",
"approximation algorithms",
"linear programming",
"instance",
"design",
"semi-definite programming",
"efficient algorithms",
"NP",
"Pi",
"approximation",
"pure mathematics",
"various approaches",
"science",
"recent research",
"tool",
"significant progress",
"Khot",
"area",
"machine learning",
"open problem",
"analysis",
"many problems",
"many important problems",
"project hierarchy",
"mathematics",
"theoretical computer science",
"computational biology",
"computer science",
"metric geometry techniques",
"Unique Games problem",
"many other areas",
"new method",
"worst case instances",
"decades",
"hardness",
"approximation algorithm",
"various combinatorial optimization problems",
"many fields",
"integrality gap",
"practice",
"problem",
"polynomial time",
"lift",
"performance",
"hierarchy",
"engineering",
"most research",
"great importance",
"close connection",
"numerous applications",
"approximate solution",
"subexponential approximation algorithms",
"operations research",
"research project",
"combinatorial optimization",
"several problems",
"combinatorial optimization problems",
"relaxation",
"real-life instances",
"many optimization problems",
"algorithmic techniques"
],
"name": "CAREER: Metric Geometry Techniques for Approximation Algorithms",
"recipient": [
{
"id": "https://www.grid.ac/institutes/grid.287491.1",
"type": "Organization"
},
{
"affiliation": {
"id": "https://www.grid.ac/institutes/grid.287491.1",
"name": "Toyota Technological Institute at Chicago",
"type": "Organization"
},
"familyName": "Makarychev",
"givenName": "Yury",
"id": "sg:person.014753561577.44",
"type": "Person"
},
{
"member": "sg:person.014753561577.44",
"roleName": "PI",
"type": "Role"
}
],
"sameAs": [
"https://app.dimensions.ai/details/grant/grant.3133011"
],
"sdDataset": "grants",
"sdDatePublished": "2019-03-07T12:35",
"sdLicense": "https://scigraph.springernature.com/explorer/license/",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com.uberresearch.data.processor/core_data/20181219_192338/projects/base/nsf_projects_5.xml.gz",
"startDate": "2012-07-01T00:00:00Z",
"type": "MonetaryGrant",
"url": "http://www.nsf.gov/awardsearch/showAward?AWD_ID=1150062&HistoricalAwards=false"
}
]
```

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/grant.3133011'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/grant.3133011'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/grant.3133011'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/grant.3133011'

This table displays all metadata directly associated to this object as RDF triples.

118 TRIPLES
19 PREDICATES
94 URIs
85 LITERALS
5 BLANK NODES

Subject | Predicate | Object | |
---|---|---|---|

1 | sg:grant.3133011 | schema:about | anzsrc-for:2201 |

2 | ″ | ″ | anzsrc-for:2208 |

3 | ″ | schema:amount | Nfeadf2261e434ca4be8c64b766830673 |

4 | ″ | schema:description | Combinatorial optimization problems are of great importance to numerous applications. They arise in operations research, machine learning, VLSI design, computational biology and many other areas. Many optimization problems however are NP-hard and thus cannot be solved exactly in polynomial time unless P=NP. It is natural therefore to look for approximation algorithms, efficient algorithms that find only approximate solutions. Design and analysis of approximation algorithms is a very active research area. Various approaches for solving combinatorial optimization problems have appeared in the last three decades. However, despite significant progress, many important problems are still open. This research project aims to advance the application of metric geometry techniques for solving combinatorial optimization problems, investigate new methods for designing approximation algorithms, and develop tools for analyzing the performance of approximation algorithms on real-life instances. This research project will be both theoretically important and practically relevant and it will lead to development of approximation algorithms for important applied problems that occur in many fields of science and engineering. Specifically, the PI will work on the following problems. * Traditionally most research has focused on analyzing the worst case performance of approximation algorithms. However, practitioners observe that instances of combinatorial optimization problems that arise in practice are often not as hard as worst case instances. The PI will study semi-random models for various combinatorial optimization problems, and develop approximation algorithms that perform well on semi-random instances. This can perhaps explain what we see in practice. * Recent research in the hardness of approximation initiated by Khot identified Unique Games Problem as a combinatorial obstacle to the development of approximation algorithms for many problems. The PI will study algorithmic techniques for solving the Unique Games Problem. * The PI will study lift-and-project hierarchies of linear programming (LP) and semi-definite programming (SDP) relaxations, analyze their integrality gaps, and design subexponential approximation algorithms that use these hierarchies. * There is a close connection between some areas of theoretical computer science and pure mathematics. To settle down some problems in combinatorial optimization, we need to resolve closely connected open problems in analysis. The PI will explore several problems with deep ties to computer science and mathematics. |

5 | ″ | schema:endDate | 2018-06-30T00:00:00Z |

6 | ″ | schema:funder | https://www.grid.ac/institutes/grid.457785.c |

7 | ″ | schema:identifier | N2817ce8db2d8473bbf41f81aa20e85af |

8 | ″ | ″ | Nacd35f5abc164303a8347110b36bf1b3 |

9 | ″ | schema:inLanguage | en |

10 | ″ | schema:keywords | Khot |

11 | ″ | ″ | NP |

12 | ″ | ″ | Pi |

13 | ″ | ″ | Unique Games problem |

14 | ″ | ″ | VLSI design |

15 | ″ | ″ | active research area |

16 | ″ | ″ | algorithmic techniques |

17 | ″ | ″ | analysis |

18 | ″ | ″ | application |

19 | ″ | ″ | approximate solution |

20 | ″ | ″ | approximation |

21 | ″ | ″ | approximation algorithm |

22 | ″ | ″ | approximation algorithms |

23 | ″ | ″ | area |

24 | ″ | ″ | career |

25 | ″ | ″ | close connection |

26 | ″ | ″ | combinatorial obstacle |

27 | ″ | ″ | combinatorial optimization |

28 | ″ | ″ | combinatorial optimization problems |

29 | ″ | ″ | computational biology |

30 | ″ | ″ | computer science |

31 | ″ | ″ | decades |

32 | ″ | ″ | deep ties |

33 | ″ | ″ | design |

34 | ″ | ″ | development |

35 | ″ | ″ | efficient algorithms |

36 | ″ | ″ | engineering |

37 | ″ | ″ | great importance |

38 | ″ | ″ | hardness |

39 | ″ | ″ | hierarchy |

40 | ″ | ″ | instance |

41 | ″ | ″ | integrality gap |

42 | ″ | ″ | lift |

43 | ″ | ″ | linear programming |

44 | ″ | ″ | machine learning |

45 | ″ | ″ | many fields |

46 | ″ | ″ | many important problems |

47 | ″ | ″ | many optimization problems |

48 | ″ | ″ | many other areas |

49 | ″ | ″ | many problems |

50 | ″ | ″ | mathematics |

51 | ″ | ″ | metric geometry techniques |

52 | ″ | ″ | most research |

53 | ″ | ″ | new method |

54 | ″ | ″ | numerous applications |

55 | ″ | ″ | open problem |

56 | ″ | ″ | operations research |

57 | ″ | ″ | performance |

58 | ″ | ″ | polynomial time |

59 | ″ | ″ | practice |

60 | ″ | ″ | practitioners |

61 | ″ | ″ | problem |

62 | ″ | ″ | project hierarchy |

63 | ″ | ″ | pure mathematics |

64 | ″ | ″ | random model |

65 | ″ | ″ | real-life instances |

66 | ″ | ″ | recent research |

67 | ″ | ″ | relaxation |

68 | ″ | ″ | research project |

69 | ″ | ″ | science |

70 | ″ | ″ | semi-definite programming |

71 | ″ | ″ | semi-random instances |

72 | ″ | ″ | several problems |

73 | ″ | ″ | significant progress |

74 | ″ | ″ | subexponential approximation algorithms |

75 | ″ | ″ | theoretical computer science |

76 | ″ | ″ | tool |

77 | ″ | ″ | various approaches |

78 | ″ | ″ | various combinatorial optimization problems |

79 | ″ | ″ | worst case instances |

80 | ″ | ″ | worst case performance |

81 | ″ | schema:name | CAREER: Metric Geometry Techniques for Approximation Algorithms |

82 | ″ | schema:recipient | Ndf4395a9b39847ce944a4b260632d47e |

83 | ″ | ″ | sg:person.014753561577.44 |

84 | ″ | ″ | https://www.grid.ac/institutes/grid.287491.1 |

85 | ″ | schema:sameAs | https://app.dimensions.ai/details/grant/grant.3133011 |

86 | ″ | schema:sdDatePublished | 2019-03-07T12:35 |

87 | ″ | schema:sdLicense | https://scigraph.springernature.com/explorer/license/ |

88 | ″ | schema:sdPublisher | N6a0a6f07054f41b0bdbdc0f793825a54 |

89 | ″ | schema:startDate | 2012-07-01T00:00:00Z |

90 | ″ | schema:url | http://www.nsf.gov/awardsearch/showAward?AWD_ID=1150062&HistoricalAwards=false |

91 | ″ | sgo:license | sg:explorer/license/ |

92 | ″ | sgo:sdDataset | grants |

93 | ″ | rdf:type | schema:MonetaryGrant |

94 | N2817ce8db2d8473bbf41f81aa20e85af | schema:name | dimensions_id |

95 | ″ | schema:value | 3133011 |

96 | ″ | rdf:type | schema:PropertyValue |

97 | N6a0a6f07054f41b0bdbdc0f793825a54 | schema:name | Springer Nature - SN SciGraph project |

98 | ″ | rdf:type | schema:Organization |

99 | Nacd35f5abc164303a8347110b36bf1b3 | schema:name | nsf_id |

100 | ″ | schema:value | 1150062 |

101 | ″ | rdf:type | schema:PropertyValue |

102 | Ndf4395a9b39847ce944a4b260632d47e | schema:member | sg:person.014753561577.44 |

103 | ″ | schema:roleName | PI |

104 | ″ | rdf:type | schema:Role |

105 | Nfeadf2261e434ca4be8c64b766830673 | schema:currency | USD |

106 | ″ | schema:value | 499988 |

107 | ″ | rdf:type | schema:MonetaryAmount |

108 | anzsrc-for:2201 | schema:inDefinedTermSet | anzsrc-for: |

109 | ″ | rdf:type | schema:DefinedTerm |

110 | anzsrc-for:2208 | schema:inDefinedTermSet | anzsrc-for: |

111 | ″ | rdf:type | schema:DefinedTerm |

112 | sg:person.014753561577.44 | schema:affiliation | https://www.grid.ac/institutes/grid.287491.1 |

113 | ″ | schema:familyName | Makarychev |

114 | ″ | schema:givenName | Yury |

115 | ″ | rdf:type | schema:Person |

116 | https://www.grid.ac/institutes/grid.287491.1 | schema:name | Toyota Technological Institute at Chicago |

117 | ″ | rdf:type | schema:Organization |

118 | https://www.grid.ac/institutes/grid.457785.c | ″ | schema:Organization |