CAREER: Metric Geometry Techniques for Approximation Algorithms View Homepage


Ontology type: schema:MonetaryGrant     


Grant Info

YEARS

2012-2018

FUNDING AMOUNT

499988 USD

ABSTRACT

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

URL

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

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




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


...