CAREER: Approximation Algorithms and Hardness of Network Optimization Problems View Homepage


Ontology type: schema:MonetaryGrant     


Grant Info

YEARS

2009-2013

FUNDING AMOUNT

460690 USD

ABSTRACT

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... »

URL

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

HOW TO GET THIS DATA PROGRAMMATICALLY:

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
 




Preview window. Press ESC to close (or click here)


...