A counterexample to Beck's conjecture on the discrepancy of three permutations
[arxiv]
with Aleksandar Nikolov.
Tight hardness results for minimizing discrepancy
[ps] [pdf]
with Moses Charikar and Aleksandar Nikolov
Proc. of the 22nd ACM-SIAM Symposium on Discrete Algorithms
(SODA 2011).
Complex semidefinite programming revisited and the assembly of
circular genomes [ps] [pdf]
with Konstantin Makarychev
Proceedings of Innovations in Computer Science
(ICS 2011).
Traveling salesman path problems [ps] [pdf]
with Fumei Lam
Mathematical Programming, Series A, 113(1): 39-59 (2008)
(Springer link).
Decision making based on approximate and smoothed pareto curves
[ps][pdf]
with Heiner Ackermann, Heiko Röglin and Berthold Vöcking
Theoretical Computer Science, 378(3): 253-270 (2007)
(Elsevier link).
Aggregating inconsistent information: Ranking and clustering
[ps] [pdf]
with Nir Ailon and Moses Charikar
Journal of the ACM, 55(5): (2008) (ACM link)
(STOC 2005 conference
version: [pdf]
).
Bounding a protein's free energy
via linear programming [ps][pdf]
with Robert D. Carr and William E. Hart
Abstract appeared as a
poster in RECOMB 2004. Results also appeared in a Sandia
Technical Report.
Cuts and orderings: On semidefinite
relaxations for the linear ordering problem
[ps][pdf]
Proceedings of APPROX 2004.
(A more comprehensive version of these results is contained in Chapters
3 and 6 of my PhD thesis (see below).)
Combinatorial problems on strings with
applications to protein folding
[ps][pdf]
with Matthias Ruhl
Proceedings of LATIN 2004.
A new algorithm for protein folding in the
HP model
[ps][pdf]
Proceedings of SODA 2002.
The maximum acyclic subgraph problem
and degree-3 graphs
[ps][pdf]
Proceedings of APPROX 2001.
Fences are futile: On relaxations for the linear
ordering problem
[ps][pdf]
with Santosh Vempala
Proceedings of IPCO 2001.
Protein structure prediction
with lattice models
[pdf]
with William E. Hart
Book chapter in Handbook of Computational Molecular Biology,
Srinivas Aluru (Editor), Chapman & Hall CRC Computer and Information
Science Series, 2006
(Publisher page).
Semidefinite programming and Unique Games
[ps][pdf][arxiv]
Lecture notes for DIMACS tutorial on limits of
approximation algorithms
(Workshop page).