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.
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
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
On rank-monotone graph operations and minimal obstruction graphs
for the Lovász-Schrijver SDP hierarchy
(with
Y. H. (Gary) Au),
Mathematical Programming A
to appear
arXiv:2401.01476.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.