Rajiv Raman


Linear Optimization Approximation Algorithms (2 credits)




Settling the APX-hardness Status for Geometric Set Cover, with Nabil Mustafa, Saurabh Ray, FOCS 2014

A separator theorem for intersecting objects in the plane, with Nabil Mustafa, Saurabh Ray, CCCG 2014.

An SDP Primal-Dual Algorithm for Approximating the Lovász-Theta Function, with T-H. Hubert Chan, Kevin L. Chang. Algorithmica 2014ISIT 2009.

On the complexity of the highway problem., with Khaled M. Elbassioni, Saurabh Ray, René Sitters. Theor. Comput. Sci. 2012SAGT 2009.

Colouring vertices of triangle-free graphs without forests, with Konrad Dabrowski, Vadim V. Lozin, Bernard Ries Discrete Mathematics, 2012,   WG 2010.

Max-coloring and online coloring with bandwidths on interval graphs, with Sriram V. Pemmaraju, Kasturi R. Varadarajan ACM Trans. Alg., 2011,   SODA 2004

Sub-Coloring and Hypo-Coloring Interval Graphs, with Rajiv Gandhi, Brad Greening, Sriram Pemmaraju Discrete Math. Alg. and Appl., 2010.,   WG 2009.

An experimental study of different approaches to solve the market equilibrium problem, with Bruno Codenotti, Benton McCune, Sriram V. Pemmaraju, Kasturi R. Varadarajan ACM Journal of Exper. Alg., 2008,   ALENEX 2005

Approximating interval coloring and max-coloring in chordal graphs, with Sriram V. Pemmaraju, Sriram Penumatcha. ACM Journal of Exper. Alg. 2005,   SEA/WEA 2004

On the Approximability of the Maximum Interval Constrained Coloring Problem, with Stefan Canzar, Khaled M. Elbassioni, Amr Elmasry. ISAAC, 2010

Cardinality Constrained Graph Partitioning into Cliques with Submodular Costs, with J. Correa, Nicole Megow, Karol Suchan CTW 2009

On the approximability of the maximum feasible subsystem problem with 0/1-coefficients, with Khaled M. Elbassioni, Rajiv Raman, Saurabh Ray, René Sitters SODA 2009

Computing Equilibrium Prices: Does Theory Meet Practice?, with Bruno Codenotti, Benton McCune, Kasturi R. Varadarajan. ESA 2005

Approximation Algorithms for the Max-coloring Problem, with Sriram V. Pemmaraju. ICALP 2005