Recent Publications

Research Interests

My research program lies in the areas of mathematical optimization, mathematics of operations research and foundations of computational mathematics. The focus of the program is on commonly encountered optimization problems (including linear and nonlinear programming and combinatorial optimization problems). The research program aims at understanding the structure of some problems in the aforementioned class and provably efficient methods for solving them.

Recent Publications

The file list.html includes a list of my publications and pointers to the ps and/or pdf files of some papers. The following is a list of recent research reports.

  • Generalized cuts and Grothendieck covers: A primal-dual approximation framework extending the Goemans-Williamson algorithm (with N. Benedetto Proença, M. K. de Carli Silva and C. M. Sato), June 2024 arXiv:2406.18670.pdf

  • On rank-monotone graph operations and minimal obstruction graphs for the Lovász-Schrijver SDP hierarchy (with Y. H. (Gary) Au), January 2024 (revised: August 2024) arXiv:2401.01476.pdf

  • A primal-dual extension of the Goemans-Williamson algorithm for the weighted fractional cut-covering problem (with N. Benedetto Proença, M. K. de Carli Silva and C. M. Sato), November 2023 arXiv:2311.15346.pdf

  • On connections between association schemes and analyses of polyhedral and positive semidefinite lift-and-project relaxations (with Y. H. (Gary) Au and N. Lindzey), August 2020 (revised: December 2023) arXiv:2008.08628.pdf

  • Everything is possible: constructing spectrahedra with prescribed facial dimensions (with V. Roshchina), SIAM Journal on Optimization to appear arXiv:2312.04419.pdf

  • Dyadic linear programming and extensions (with A. Abdi, G. Cornuéjols and B. Guenin), Mathematical Programming A to appear arXiv:2309.04601.pdf

  • Stable set polytopes with high lift-and-project ranks for the Lovász-Schrijver SDP operator (with Y. H. (Gary) Au), Mathematical Programming A to appear arXiv:2303.08971.pdf

  • Computational complexity of decomposing a symmetric matrix as a sum of positive semidefinite and diagonal matrices (with S. A. Vavasis and J. Xu), Foundations of Computational Mathematics to appear arXiv:2209.05678.pdf

  • Efficient implementation of interior-point methods for quantum relative entropy (with M. Karimi), INFORMS Journal on Computing to appear arXiv:2312.07438.pdf, software

  • Total dual dyadicness and dyadic generating sets (with A. Abdi, G. Cornuéjols and B. Guenin), Mathematical Programming B 206 (2024) 125-143. arXiv:2111.05749.pdf. This is the full version of the conference article (IPCO 2022) with the same title below.

  • Graphs with large girth and chromatic number are hard for Nullstellensatz (with J. Romero), SIAM Journal on Discrete Math. 38 (2024) 2108-2131. arXiv:2212.05365.pdf

  • Domain-Driven Solver (DDS) version 2.1: a MATLAB based software package for convex optimization problems in domain-driven form (with M. Karimi), Mathematical Programming Computation 16 (2024) 37-92 arXiv:1908.03075.pdf , software

  • Linear optimization over homogeneous matrix cones (with L. Vandenberghe), Acta Numerica 32 (2023) 675-747 arXiv:2211.00761.pdf The final publication is available at DOI

  • Testing idealness in the filter oracle model (with A. Abdi, G. Cornuéjols and B. Guenin), Operations Research Letters 50 (2022) 753-755 arXiv:2202.07299.pdf The final publication is available at DOI

  • Total dual dyadicness and dyadic generating sets (with A. Abdi, G. Cornuéjols and B. Guenin), Proceedings of the 23rd International Conference on Integer Programming and Combinatorial Optimization (IPCO 2022), Eindhoven, The Netherlands, June 27-29, 2022, Lecture Notes in Computer Science, Springer 2022, pp. 1-14. Available at DOI. Full version is above.

  • Status determination by interior-point methods for convex optimization problems in domain-driven form (with M. Karimi), Mathematical Programming A 194 (2022) 937-974 arXiv:1901.007084.pdf The final publication is available at DOI

  • Clean clutters and dyadic fractional packings (with A. Abdi, G. Cornuéjols and B. Guenin), SIAM Journal on Discrete Math. 36 (2022) 1012-1037 dyadic.pdf The final publication is available at DOI

  • On the spectral structure of Jordan-Kronecker products of symmetric and skew-symmetric matrices (with N. Kalantarova), Linear Algebra and its Applications 608 (2021) 343-362 arXiv:1805.09737.pdf The final publication is available at DOI

  • Primal-dual interior-point methods for domain-driven formulations (with M. Karimi), Mathematics of Operations Research 45 (2020) 591-621 arXiv:1804.06925.pdf The final publication is available at DOI

  • A notion of total dual integrality for convex, semidefinite, and extended formulations, (with M. K. de Carli Silva), SIAM Journal on Discrete Math. 34 (2020) 470-496 arXiv:1801.09155.pdf The final publication is available at DOI

  • Approximation ratio of LD algorithm for multi-processor scheduling and the Coffman-Sethi conjecture (with P. S. Ravi), Information Processing Letters 159-160 (2020) article 105959 arXiv:1505.01005.pdf

  • Strict complementarity in semidefinite optimization with elliptopes including the MaxCut SDP (with M. K. de Carli Silva), SIAM Journal on Optimization 29 (2019) 2650-2676 arXiv:1806.01173.pdf The final publication is available at DOI

  • Facially dual complete (nice) cones and lexicographic tangents (with V. Roshchina), SIAM Journal on Optimization 29 (2019) 2363-2387 arXiv:1704.06368.pdf

  • Elementary polytopes with high lift-and-project ranks for strong positive semidefinite operators (with Y. H. (Gary) Au), Discrete Optimization 27 (2018) 103-129 arXiv:1608.07647.pdf The final publication is available at DOI

  • Pointed closed convex sets are the intersection of all rational supporting closed halfspaces (with M. K. de Carli Silva), February 2018 arXiv:1802.03296.pdf

  • Quantum and classical coin-flipping protocols based on bit-commitment and their point games (with A. Nayak and J. Sikora), April 2015 arXiv:1504.04217.pdf

  • Interior-point algorithms for convex optimization based on primal-dual metrics (with T. G. J. Myklebust), November 2014 (revised: April 2016) arXiv:1411.2129.pdf

  • A utility theory based interactive approach to robustness in linear optimization (with M. Karimi and S. Moazeni), Journal of Global Optimization 70 (2018) 811-842 arXiv:1312.4489.pdf The final publication is available at Springer via DOI

  • An axiomatic duality framework for the theta body and related convex corners (with M. K. de Carli Silva), Mathematical Programming A 162 (2017) 283-322 arXiv:1412.2103.pdf. The final publication is available at Springer via DOI

  • Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs (with S. M. Bianchi, M. S. Escalante and G. L. Nasini), Mathematical Programming A 162 (2017) 201-223 arXiv:1411.2069.pdf. The final publication is available at Springer via DOI

  • Primal-dual entropy based interior-point algorithms for linear optimization (with M. Karimi and S. Luo), RAIRO Operations Research 51 (2017) 299-328 arXiv:1410.8226.pdf The final publication is available at DOI

  • Polynomial optimization with a focus on hyperbolic polynomials Oberwolfach Reports OWR-2017-14 (2017) 797-800 OWR-2017-14.pdf

  • Worst-case performance analysis of some approximation algorithms for minimizing makespan and flowtime (with P. S. Ravi and M. Huang), Journal of Scheduling 19 (2016) 547-561 arXiv:1312.3345.pdf. The final publication is available at Springer via DOI

  • A comprehensive analysis of polyhedral lift-and-project methods (with Y. H. (Gary) Au), SIAM Journal on Discrete Math. 30 (2016) 411-451 arXiv:1312.5972.pdf

  • A search for quantum coin-flipping protocols using optimization techniques (with A. Nayak and J. Sikora), Mathematical Programming A 156 (2016) 581-613 arXiv:1403.0505.pdf, arXiv:1403.0505-supplemental-material.pdf, source codes. The final publication is available at Springer via DOI

  • Local superlinear convergence of polynomial-time interior-point methods for hyperbolicity cone optimization problems (with Yu. Nesterov), SIAM Journal on Optimization 26 (2016) 139-170 arXiv:1412.1857.pdf

  • Perturbed sums of squares theorem for polynomial optimization and its applications (with M. Muramatsu and H. Waki), Optimization Methods and Software 31 (2016) 134-156 arXiv:1304:0065.pdf.

  • Efficient heuristic algorithms for maximum utility product pricing problems (with T. G. J. Myklebust and M. A. Sharpe), Computers and Operations Research 69 (2016) 25-39 pricedown.pdf, source codes and data.

    [ICO]NameLast modifiedSizeDescription
    [PARENTDIR]Parent Directory  -  
    [ ]1010.6036.pdf2012-09-28 11:49 174K 
    [ ]1309.7415.pdf2014-07-27 17:47 565K 
    [ ]1312.3345.pdf2015-09-06 21:42 356K 
    [ ]1312.4489.pdf2017-10-25 16:17 507K 
    [ ]1312.5972.pdf2015-12-02 00:34 542K 
    [ ]1403.0505-supplemental.pdf2015-04-07 10:48 704K 
    [ ]1403.0505.pdf2015-04-07 10:47 412K 
    [ ]1410.8226.pdf2016-02-22 09:12 580K 
    [ ]1411.2069.pdf2016-03-23 14:46 400K 
    [ ]1411.2129.pdf2016-04-07 08:33 434K 
    [ ]1412.1857.pdf2015-08-31 09:48 461K 
    [ ]1412.2103.pdf2016-04-07 16:02 469K 
    [ ]1504.04217.pdf2015-04-17 09:04 1.0M 
    [ ]1505.01005.pdf2019-12-08 23:54 318K 
    [ ]1608.07647.pdf2017-06-29 15:21 509K 
    [ ]1704.06368.pdf2019-05-16 00:26 1.6M 
    [ ]1801.09155.pdf2018-01-30 11:19 593K 
    [ ]1802.03296.pdf2018-06-14 15:17 460K 
    [ ]1804.06925.pdf2018-04-20 15:22 831K 
    [ ]1805.09737.pdf2020-08-07 20:24 137K 
    [ ]1806.01173.pdf2019-02-08 10:31 611K 
    [ ]1901.07084.pdf2019-01-21 16:17 611K 
    [ ]1908.03075.pdf2023-09-19 11:34 799K 
    [ ]2008.08628.pdf2024-01-01 13:30 446K 
    [ ]2111.05749.pdf2023-01-23 20:25 297K 
    [ ]2202.07299.pdf2022-11-01 20:48 173K 
    [ ]2209.05678.pdf2023-11-27 23:16 446K 
    [ ]2211.00761.pdf2022-11-03 09:57 617K 
    [ ]2212.05365.pdf2024-02-12 11:32 790K 
    [ ]2303.08971.pdf2024-04-30 15:08 592K 
    [ ]2309.04601.pdf2024-04-11 09:42 463K 
    [ ]2311.15346.pdf2023-11-28 10:37 901K 
    [ ]2312.04419.pdf2024-08-23 10:02 2.6M 
    [ ]2312.07438.pdf2024-10-01 10:24 328K 
    [ ]2401.01476.pdf2024-08-21 15:06 424K 
    [ ]2406.18670.pdf2024-06-28 10:30 653K 
    [ ]BENT_DAM.pdf2012-11-12 13:34 345K 
    [ ]CGJ-SVVA2.pdf2009-04-14 13:29 184K 
    [ ]HCCP-P.pdf2010-11-11 18:07 201K 
    [TXT]HEADER.html2024-09-29 14:28 17K 
    [ ]IOR-invited-survey.pdf2008-08-28 14:24 231K 
    [ ]OWR-2017-14.pdf2018-01-02 16:21 189K 
    [ ]Shioda-Tuncel-Hui.pdf2009-02-13 17:45 464K 
    [ ]arxivMWT2013.pdf2015-03-02 14:13 370K 
    [ ]coap-STM.pdf2009-05-08 17:36 320K 
    [ ]corr99-37.pdf2006-11-06 10:19 249K 
    [ ]corr99-37.ps1999-09-11 18:03 282K 
    [ ]corr2000-01.pdf2016-08-04 16:20 241K 
    [ ]corr2000-01.ps2001-04-09 13:05 263K 
    [ ]corr2000-33.pdf2006-11-06 10:20 438K 
    [ ]corr2000-33.ps2001-04-24 17:42 404K 
    [ ]corr2002-10.pdf2006-11-06 10:20 365K 
    [ ]corr2002-10.ps2002-07-11 12:43 310K 
    [ ]corr2002-13.pdf2006-11-06 10:21 361K 
    [ ]corr2002-13.ps2003-02-07 16:34 317K 
    [ ]corr2002-15.ps2003-06-27 14:59 269K 
    [ ]corr2002-32.pdf2006-11-06 10:20 350K 
    [ ]corr2002-32.ps2004-05-31 08:28 296K 
    [ ]corr2003-16.pdf2006-11-06 10:17 212K 
    [ ]corr2003-16.ps2004-05-08 11:38 129K 
    [ ]corr2003-20.pdf2006-11-06 10:19 318K 
    [ ]corr2003-20.ps2004-05-31 09:56 262K 
    [ ]corr2003-24.pdf2006-11-06 10:21 281K 
    [ ]corr2003-24.ps2004-11-09 16:46 217K 
    [ ]corr2004-05.pdf2007-06-04 11:06 252K 
    [ ]corr2004-05.ps2007-06-04 11:05 3.1M 
    [ ]corr2004-18.pdf2006-11-28 14:19 242K 
    [ ]corr2005-12.pdf2006-01-23 10:47 711K 
    [ ]corr2006-18.pdf2008-07-18 09:22 288K 
    [ ]corr2006-19.pdf2008-05-24 20:27 288K 
    [ ]corr2006-24r.pdf2008-04-04 13:31 253K 
    [ ]corr2007-03.pdf2010-05-14 20:50 333K 
    [ ]corr2007-07.pdf2010-07-27 13:41 127K 
    [ ]corr2007-17.pdf2008-07-01 12:03 169K 
    [ ]corr2008-03.pdf2008-10-08 16:54 135K 
    [ ]corr2008-04.pdf2009-04-14 13:29 240K 
    [ ]corr2008-07.pdf2012-02-06 17:44 512K 
    [ ]corr2008-12.pdf2010-06-01 09:44 219K 
    [ ]dyadic.pdf2020-09-16 16:07 667K 
    [ ]errata-1010.6036.pdf2016-03-09 08:30 190K 
    [ ]errata-additional-material.pdf2014-12-06 10:39 84K 
    [ ]icbme2008.pdf2009-02-13 17:58 147K 
    [TXT]list.html2024-10-01 10:52 44K 
    [ ]math-prog-2002-15.pdf2006-11-06 10:18 263K 
    [ ]math-prog-2002-15.ps2003-06-27 14:59 203K 
    [ ]minmax-link.pdf2012-09-28 12:05 304K 
    [ ]monotonicity.pdf2006-11-06 10:19 198K 
    [ ]monotonicity.ps1996-12-04 14:08 165K 
    [ ]mrop.pdf2006-11-06 10:18 160K 
    [ ]mrop.ps1996-11-20 14:27 152K 
    [ ]nonconvex.pdf2006-11-06 10:18 236K 
    [ ]nonconvex.ps2000-03-22 09:22 633K 
    [ ]pricedown.pdf2015-12-01 17:10 401K 
    [ ]pseudo-poly.pdf2006-11-06 10:18 199K 
    [ ]pseudo-poly.ps1996-11-20 14:26 173K 
    [ ]relative-strength-intersection-cuts.pdf2014-03-07 16:38 762K 
    [ ]strong-duality.pdf2006-11-06 10:17 180K 
    [ ]strong-duality.ps1997-09-25 10:09 1.1M 
    [ ]suff-LMR.pdf2012-06-01 01:24 308K 
    [ ]survey-TOR1.pdf2006-09-27 10:07 198K 
    [ ]triangulation.pdf2006-11-06 10:17 242K 
    [ ]triangulation.ps1996-11-20 14:53 254K 
    Apache/2.4.52 (Ubuntu) Server at www.math.uwaterloo.ca Port 443