Amit Agarwal

STOC Conference 2007 Conference Paper

Improved approximation for directed cut problems

• Amit Agarwal
• Noga Alon
• Moses Charikar

We present improved approximation algorithms for directed multicutand directed sparsest cut. The current best known approximationratio for these problems is O(n 1/2 ). We obtain an Õ(n 11/23 )-approximation. Our algorithm works with thenatural LP relaxation used in prior work. We use a randomized roundingalgorithm with a more sophisticated charging scheme and analysis toobtain our improvement. This also implies a Õ(n 11/23 ) upper bound on the ratio between the maximum multicommodity flowand minimum multicut in directed graphs.

STOC Conference 2005 Conference Paper

O(sqrt(log n)) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems

• Amit Agarwal
• Moses Charikar
• Konstantin Makarychev
• Yury Makarychev

ICAPS Conference 2003 Conference Paper

The Role of Planning in Grid Computing

• Jim Blythe
• Ewa Deelman
• Yolanda Gil
• Carl Kesselman
• Amit Agarwal
• Gaurang Mehta
• Karan Vahi

Grid computing gives users access to widely distributed networks of computing resources to solve large-scale tasks such as scientific computation. These tasks are defined as standalone components that can be combined to process the data in various ways. We have implemented a planning system to generate task workflows for the Grid automatically, allowing the user to specify the desired data products in simple terms. The planner uses heuristic control rules and searches a number of alternative complete plans in order to find a high-quality solution. We describe an implemented test case in gravitational wave interferometry and show how the planner is integrated in the Grid environment. We discuss promising future directions of this work. We believe AI planning will play a crucial role in developing complex application workflows for the Grid.