Ontology type: schema:MonetaryGrant

2009-2013

460690 USD

CAREER: Approximation Algorithms and Hardness of Network Optimization Problems Julia Chuzhoy Network optimization problems play a central role in combinatorial optimization, and they arise in virtually every area of computer science. Since many such problems are NP-hard, a natural approach is to settle for efficient algorithms that produce near-optimal, or approximate, solutions. Many powerful algorithmic paradigms, and techniques used in proving lower bounds on approximability, have been developed in the context of network optimization problems, leading to a better understanding of many important problems in this class. Despite this progress, some of the most fundamental network optimization problems remain poorly understood. This research will focus on central open problems in the areas of graph partitioning, graph coloring, network design and network routing. One goal of this research is to advance the understanding of the approximability of these problems. The PI would also like to explore the connections between algorithm design and hardness of approximation proofs, and to combine tools developed in the areas of approximation algorithms, graph theory, hardness of approximation and probabilistically checkable proofs in exploring the approximability of network optimization problems. Better approximation algorithms for network optimization problems will lead to improved performance for many applications, and will most probably require the development of new algorithmic paradigms. Understanding and isolating features that make problems intractable will help in finding better formulation for practical problems in the framework of combinatorial optimization, when such features can be avoided. The educational component of this project includes introducing a new course on approximation of network optimization problems. The PI will also participate in activities aimed at encouraging a broader involvement of women in research in theoretical computer science. These activities include participation in workshops and mentorship programs whose target audience is advanced undergraduate and graduate female students. More... »

http://www.nsf.gov/awardsearch/showAward?AWD_ID=0844872&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": "460690"
},
"description": "CAREER: Approximation Algorithms and Hardness of Network Optimization Problems Julia Chuzhoy Network optimization problems play a central role in combinatorial optimization, and they arise in virtually every area of computer science. Since many such problems are NP-hard, a natural approach is to settle for efficient algorithms that produce near-optimal, or approximate, solutions. Many powerful algorithmic paradigms, and techniques used in proving lower bounds on approximability, have been developed in the context of network optimization problems, leading to a better understanding of many important problems in this class. Despite this progress, some of the most fundamental network optimization problems remain poorly understood. This research will focus on central open problems in the areas of graph partitioning, graph coloring, network design and network routing. One goal of this research is to advance the understanding of the approximability of these problems. The PI would also like to explore the connections between algorithm design and hardness of approximation proofs, and to combine tools developed in the areas of approximation algorithms, graph theory, hardness of approximation and probabilistically checkable proofs in exploring the approximability of network optimization problems. Better approximation algorithms for network optimization problems will lead to improved performance for many applications, and will most probably require the development of new algorithmic paradigms. Understanding and isolating features that make problems intractable will help in finding better formulation for practical problems in the framework of combinatorial optimization, when such features can be avoided. The educational component of this project includes introducing a new course on approximation of network optimization problems. The PI will also participate in activities aimed at encouraging a broader involvement of women in research in theoretical computer science. These activities include participation in workshops and mentorship programs whose target audience is advanced undergraduate and graduate female students.",
"endDate": "2013-12-31T00:00:00Z",
"funder": {
"id": "https://www.grid.ac/institutes/grid.457785.c",
"type": "Organization"
},
"id": "sg:grant.3095605",
"identifier": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"3095605"
]
},
{
"name": "nsf_id",
"type": "PropertyValue",
"value": [
"0844872"
]
}
],
"inLanguage": [
"en"
],
"keywords": [
"new course",
"project",
"approximation algorithms",
"theoretical computer science",
"research",
"many important problems",
"educational component",
"Network Optimization Problems Julia Chuzhoy Network optimization problems",
"network design",
"participation",
"target audience",
"central role",
"class",
"area",
"performance",
"tool",
"graph theory",
"progress",
"approximability",
"features",
"fundamental network optimization problems",
"many applications",
"better understanding",
"practical problems",
"best formulation",
"efficient algorithms",
"network routing",
"development",
"lower bounds",
"broad involvement",
"understanding",
"Pi",
"checkable proofs",
"technique",
"such features",
"network optimization problems",
"many such problems",
"computer science",
"graph partitioning",
"context",
"graph coloring",
"problem",
"activity",
"Many powerful algorithmic paradigms",
"workshop",
"mentorship program",
"career",
"women",
"combinatorial optimization",
"approximation proofs",
"natural approach",
"new algorithmic paradigms",
"algorithm design",
"goal",
"framework",
"central open problem",
"Better Approximation Algorithms",
"approximation",
"connection",
"hardness",
"NP",
"solution",
"Network Optimization Problems",
"graduate female students"
],
"name": "CAREER: Approximation Algorithms and Hardness of Network Optimization Problems",
"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": "Chuzhoy",
"givenName": "Julia",
"id": "sg:person.016617773333.51",
"type": "Person"
},
{
"member": "sg:person.016617773333.51",
"roleName": "PI",
"type": "Role"
}
],
"sameAs": [
"https://app.dimensions.ai/details/grant/grant.3095605"
],
"sdDataset": "grants",
"sdDatePublished": "2019-03-07T12:33",
"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_3.xml.gz",
"startDate": "2009-01-01T00:00:00Z",
"type": "MonetaryGrant",
"url": "http://www.nsf.gov/awardsearch/showAward?AWD_ID=0844872&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.3095605'

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

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

Turtle is a human-readable linked data format.

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

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

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

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

111 TRIPLES
19 PREDICATES
87 URIs
78 LITERALS
5 BLANK NODES

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

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

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

3 | ″ | schema:amount | N5a8652baad34458e8445a583bb723e9d |

4 | ″ | schema:description | CAREER: Approximation Algorithms and Hardness of Network Optimization Problems Julia Chuzhoy Network optimization problems play a central role in combinatorial optimization, and they arise in virtually every area of computer science. Since many such problems are NP-hard, a natural approach is to settle for efficient algorithms that produce near-optimal, or approximate, solutions. Many powerful algorithmic paradigms, and techniques used in proving lower bounds on approximability, have been developed in the context of network optimization problems, leading to a better understanding of many important problems in this class. Despite this progress, some of the most fundamental network optimization problems remain poorly understood. This research will focus on central open problems in the areas of graph partitioning, graph coloring, network design and network routing. One goal of this research is to advance the understanding of the approximability of these problems. The PI would also like to explore the connections between algorithm design and hardness of approximation proofs, and to combine tools developed in the areas of approximation algorithms, graph theory, hardness of approximation and probabilistically checkable proofs in exploring the approximability of network optimization problems. Better approximation algorithms for network optimization problems will lead to improved performance for many applications, and will most probably require the development of new algorithmic paradigms. Understanding and isolating features that make problems intractable will help in finding better formulation for practical problems in the framework of combinatorial optimization, when such features can be avoided. The educational component of this project includes introducing a new course on approximation of network optimization problems. The PI will also participate in activities aimed at encouraging a broader involvement of women in research in theoretical computer science. These activities include participation in workshops and mentorship programs whose target audience is advanced undergraduate and graduate female students. |

5 | ″ | schema:endDate | 2013-12-31T00:00:00Z |

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

7 | ″ | schema:identifier | N7f77ca4fcfd2487bb2298b846c8f5b0b |

8 | ″ | ″ | Na94545f5d3cc4c5ebad2533eedfdea20 |

9 | ″ | schema:inLanguage | en |

10 | ″ | schema:keywords | Better Approximation Algorithms |

11 | ″ | ″ | Many powerful algorithmic paradigms |

12 | ″ | ″ | NP |

13 | ″ | ″ | Network Optimization Problems |

14 | ″ | ″ | Network Optimization Problems Julia Chuzhoy Network optimization problems |

15 | ″ | ″ | Pi |

16 | ″ | ″ | activity |

17 | ″ | ″ | algorithm design |

18 | ″ | ″ | approximability |

19 | ″ | ″ | approximation |

20 | ″ | ″ | approximation algorithms |

21 | ″ | ″ | approximation proofs |

22 | ″ | ″ | area |

23 | ″ | ″ | best formulation |

24 | ″ | ″ | better understanding |

25 | ″ | ″ | broad involvement |

26 | ″ | ″ | career |

27 | ″ | ″ | central open problem |

28 | ″ | ″ | central role |

29 | ″ | ″ | checkable proofs |

30 | ″ | ″ | class |

31 | ″ | ″ | combinatorial optimization |

32 | ″ | ″ | computer science |

33 | ″ | ″ | connection |

34 | ″ | ″ | context |

35 | ″ | ″ | development |

36 | ″ | ″ | educational component |

37 | ″ | ″ | efficient algorithms |

38 | ″ | ″ | features |

39 | ″ | ″ | framework |

40 | ″ | ″ | fundamental network optimization problems |

41 | ″ | ″ | goal |

42 | ″ | ″ | graduate female students |

43 | ″ | ″ | graph coloring |

44 | ″ | ″ | graph partitioning |

45 | ″ | ″ | graph theory |

46 | ″ | ″ | hardness |

47 | ″ | ″ | lower bounds |

48 | ″ | ″ | many applications |

49 | ″ | ″ | many important problems |

50 | ″ | ″ | many such problems |

51 | ″ | ″ | mentorship program |

52 | ″ | ″ | natural approach |

53 | ″ | ″ | network design |

54 | ″ | ″ | network optimization problems |

55 | ″ | ″ | network routing |

56 | ″ | ″ | new algorithmic paradigms |

57 | ″ | ″ | new course |

58 | ″ | ″ | participation |

59 | ″ | ″ | performance |

60 | ″ | ″ | practical problems |

61 | ″ | ″ | problem |

62 | ″ | ″ | progress |

63 | ″ | ″ | project |

64 | ″ | ″ | research |

65 | ″ | ″ | solution |

66 | ″ | ″ | such features |

67 | ″ | ″ | target audience |

68 | ″ | ″ | technique |

69 | ″ | ″ | theoretical computer science |

70 | ″ | ″ | tool |

71 | ″ | ″ | understanding |

72 | ″ | ″ | women |

73 | ″ | ″ | workshop |

74 | ″ | schema:name | CAREER: Approximation Algorithms and Hardness of Network Optimization Problems |

75 | ″ | schema:recipient | Nc4e3b084dd614c32895229cc739cc302 |

76 | ″ | ″ | sg:person.016617773333.51 |

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

78 | ″ | schema:sameAs | https://app.dimensions.ai/details/grant/grant.3095605 |

79 | ″ | schema:sdDatePublished | 2019-03-07T12:33 |

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

81 | ″ | schema:sdPublisher | Ndbf56a04ad064b218834208cfc0d292a |

82 | ″ | schema:startDate | 2009-01-01T00:00:00Z |

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

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

85 | ″ | sgo:sdDataset | grants |

86 | ″ | rdf:type | schema:MonetaryGrant |

87 | N5a8652baad34458e8445a583bb723e9d | schema:currency | USD |

88 | ″ | schema:value | 460690 |

89 | ″ | rdf:type | schema:MonetaryAmount |

90 | N7f77ca4fcfd2487bb2298b846c8f5b0b | schema:name | nsf_id |

91 | ″ | schema:value | 0844872 |

92 | ″ | rdf:type | schema:PropertyValue |

93 | Na94545f5d3cc4c5ebad2533eedfdea20 | schema:name | dimensions_id |

94 | ″ | schema:value | 3095605 |

95 | ″ | rdf:type | schema:PropertyValue |

96 | Nc4e3b084dd614c32895229cc739cc302 | schema:member | sg:person.016617773333.51 |

97 | ″ | schema:roleName | PI |

98 | ″ | rdf:type | schema:Role |

99 | Ndbf56a04ad064b218834208cfc0d292a | schema:name | Springer Nature - SN SciGraph project |

100 | ″ | rdf:type | schema:Organization |

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

102 | ″ | rdf:type | schema:DefinedTerm |

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

104 | ″ | rdf:type | schema:DefinedTerm |

105 | sg:person.016617773333.51 | schema:affiliation | https://www.grid.ac/institutes/grid.287491.1 |

106 | ″ | schema:familyName | Chuzhoy |

107 | ″ | schema:givenName | Julia |

108 | ″ | rdf:type | schema:Person |

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

110 | ″ | rdf:type | schema:Organization |

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