BEGIN:VCALENDAR VERSION:2.0 PRODID:-//Drupal iCal API//EN X-WR-CALNAME:Events items teaser X-WR-TIMEZONE:America/Toronto BEGIN:VTIMEZONE TZID:America/Toronto X-LIC-LOCATION:America/Toronto BEGIN:DAYLIGHT TZNAME:EDT TZOFFSETFROM:-0500 TZOFFSETTO:-0400 DTSTART:20260308T070000 END:DAYLIGHT BEGIN:STANDARD TZNAME:EST TZOFFSETFROM:-0400 TZOFFSETTO:-0500 DTSTART:20251102T060000 END:STANDARD END:VTIMEZONE BEGIN:VEVENT UID:6a7235ceea7f9 DTSTART;TZID=America/Toronto:20260807T100000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20260807T110000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/masters-thes is-presentation-ziwen-wang-solving-linear SUMMARY:Master's Thesis Presentation - ZiWen Wang - Solving Linear Programs \nwith very Tall Constraint Matrices CLASS:PUBLIC DESCRIPTION:SPEAKER: \n ZiWen Wang\n\nSUPERVISOR:\n Levent Tuncel\n\nLOCAT ION:\n MC 5479\n\nABSTRACT: \n\nGiven an LP with tall and skinny constrai nt matrix\, we will\nexploit this property and study an algorithm invent ed by Clarkson\n[8]. Although this algorithm has\nbeen around for over 30 years\, there were no software or\nimplementation that could be found on line\, nor there be any\nbenchmarks for these special tall and skinny LP s. We will describe\nsome variants and changes to the algorithm aiming f or practical\nperformancesto close this gap.\n\nWe also study a first orde r algorithm aimed for large scale LP\ns proposed by a group of researche rs from Google [2]\, [3] called\nPDLP. And compare it with Clarkson’s a lgorithm. DTSTAMP:20260804T185614Z END:VEVENT BEGIN:VEVENT UID:6a7235ceebf6a DTSTART;TZID=America/Toronto:20260807T110000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20260807T120000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/masters-thes is-presentation-amaan-khan-study-first-order SUMMARY:Master's Thesis Presentation - Amaan Khan - A Study of First-Order\ nPrimal-Dual Algorithms for Linear Optimization CLASS:PUBLIC DESCRIPTION:SPEAKER: \n Amaan Khan\n\nSUPERVISOR:\n Levent Tuncel\n\nLOCAT ION: \n MC 5479\n\nABSTRACT: \n\nSecond-order Interior Point Methods (IP M) have been studied\nextensively over the past 80 years\, proving effecti ve for conic\noptimization. They can produce high-precision approximate so lutions in\nfew iterations. Each iteration is computationally expensive: T he core\nof each iteration is a large matrix inversion that scales poorly with\nthe number of variables.\n\nIn large-scale applications\, we cannot bear the per-iteration cost\n(perhaps due to lack of memory)\, so we inste ad turn to first-order\nmethods. We study a first-order IPM that uses a lo w-rank update scheme\nto replace the matrix inversion with significantly l ower per-iteration\ncost\, and compare this to other first-order methods f or solving LP at\nscale. DTSTAMP:20260804T185614Z END:VEVENT BEGIN:VEVENT UID:6a7235ceecfd4 DTSTART;TZID=America/Toronto:20260807T153000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20260807T163000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/tutte-colloq uium-michael-friedlander-measure-cone-randomness SUMMARY:Tutte Colloquium -Michael Friedlander-The Measure of a Cone:\nRando mness and exactness in convex optimization CLASS:PUBLIC DESCRIPTION:SPEAKER:\n Michael Friedlander\n\nAFFILIATION:\n University of British Columbia.\n\nLOCATION:\n MC 5501\n\nABSTRACT: Conic geometry enco des combinatorial properties of a convex\nprogram. Under a probabilistic model of the data\, these combinatorial\nproperties become random events. Their likelihood is the measure of a\ncone. We illustrate this view with a dual pair of questions. First\,\nhow much can a linear program be regu larized before its solution\nchanges? With random costs\, the answer turn s on the Gaussian measure\nof the solution's normal cone. Second\, how ma ny measurements are\nneeded to separate a superposition of structured sig nals? Here\, each\nsignal's complexity is the statistical dimension of its  descent cone.\nA convex program recovers the components once the measure ment count\nexceeds the total complexity.\n\nBased on joint work with Sha rvaj Kubal\, Yaniv Plan\, and Matthew Scott\;\nZhenan Fan\, Halyun Jeong\ , and Babhru Joshi\; and Ives Macêdo and Ting\nKei Pong. DTSTAMP:20260804T185614Z END:VEVENT BEGIN:VEVENT UID:6a7235ceee813 DTSTART;TZID=America/Toronto:20260810T140000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20260810T150000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/masters-thes is-presentation-david-evangelista-backedge SUMMARY:Master's Thesis Presentation - David Evangelista - Backedge Graphs of\nTournaments: Algorithms and Complexity CLASS:PUBLIC DESCRIPTION:SPEAKER:\n David Evangelista\n\nSUPERVISOR(S):\n Joseph Cheriya n and Sophie Spirkl\n\nCOMMITTEE:\n Jane Gao\, Eric Blais\n\nLOCATION:\n M C 5417\n\nABSTRACT: \n\nA tournament $\\T=(V\,A)$ on $n$ vertices is an o rientation of the\ncomplete graph $K_n$. The backedge graph of $T$ with re spect to an\nordering of $V$ is the undirected graph on vertex set $V$ who se edge\nset corresponds to the arcs directed from a later vertex to an ea rlier\nvertex in the ordering. Backedge graphs provide concise\nrepresenta tions of the tournament. The algorithmic problem of\ndetermining whether a tournament admits a backedge graph in a given\nclass of undirected graphs varies in complexity\, and is often\nequivalent to computing parameters o f tournaments\, such as\ndegreewidth when the backedge graph has bounded maximum degree\n\\cite{Davot et al.\, 2023}. We extend the notion of degre ewidth by\nintroducing directional degreewidth\, which separately bounds t he\nleft-degrees and right-degrees of vertices in addition to bounding the \ntotal degrees. We obtain an algorithm for verifying bounds on the\ndirec tional degreewidth of the tournament\, whose runtime is polynomial\ntime w hen the total degree is unbounded\, or fixed-parameter tractable\ntime wit h respect to the total degree bound otherwise. We also provide\na polynomi al-time algorithm for computing a $P_3$-free backedge graph\nof a tourname nt\, if it exists. Together with existing results\, the\nlatter result set tles the complexity of determining whether a\ntournament admits an $H$-fre e backedge graph when $H$ is any graph on\nthree vertices. DTSTAMP:20260804T185614Z END:VEVENT BEGIN:VEVENT UID:6a7235ceef84e DTSTART;TZID=America/Toronto:20260806T130000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20260806T160000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/phd-defense- leo-jung-preprocessing-hard-optimization SUMMARY:PhD Defense - Leo Jung - Preprocessing for Hard Optimization Proble ms\nAcross Structurally Diverse Models CLASS:PUBLIC DESCRIPTION:SPEAKER:\n\nLeo Jung\n\nLOCATION:\n MC 5029\n\nABSTRACT: \n\nD ifficulties in solving large-scale optimization problems often arise\nfrom structural pathologies such as ill-conditioning\, Hadamard\nill-posedness \, and degeneracy\, particularly due to the failure of\nconstraint qualifi cations. While standard algorithms often struggle to\naddress these issues \, preprocessing based on structural analysis\noffers an effective strateg y for overcoming such challenges. This\nthesis investigates several prepro cessing methods targeting various\nsources of these difficulties. \nIn Par t I\, we study a nonclassical\, average condition number of linear\nsystem s\, the $\\omega$-condition number. Our results demonstrate\nseveral advan tages of the $\\omega$-condition number over the classical\n$\\kappa$-cond ition number. First\, $\\omega$ provides a more accurate\nmeasure of the c onditioning of linear systems by more faithfully\ncapturing the effects of perturbations observed in practice. Second\,\n$\\omega$ exhibits superior numerical stability compared to $\\kappa$.\nThird\, when used in precondi tioner design\, $\\omega$ more effectively\npromotes eigenvalue clustering \, which is crucial for the efficiency of\niterative solvers. Finally\, th e analytical simplicity of $\\omega$\nenables the derivation of explicit o ptimality conditions\, allowing for\nclosed-form expressions of optimal pr econditioners under various\nframeworks\, including low rank updates of th e generalized Jacobian for\nsemismooth Newton methods and diagonal or bloc k-diagonal scaling. For\ndiagonal preconditioning\, we further include a c omparison between two\ndistinct notions of conditioning. \nIn Part II\, we first answer in the affirmative a long-standing open\nquestion of whether the smooth stress function admits local nonglobal\nminimizers. This quart ic nonconvex objective function arises in the\nexact recovery of a Euclide an distance matrix (EDM) of a given\nembedding dimension. By eliminating t he Hadamard ill-posedness caused\nby translation and rotation invariance\, we stabilize Newton's method\nand avoid singular Hessians. \\\\ \nWe then consider the single-element error correction problem as a case\nstudy. We first show that the standard nearest EDM formulation based\non minimizing the smooth stress function fails to recover the correct\nEDM in this sett ing. We then introduce divide-and-conquer strategies\nbased on facial redu ction. Our approach efficiently recovers the\ncorrect EDM with high accura cy\, and we further provide criteria\ncharacterizing the existence of mult iple solutions. \nIn Part III\, we relate FR to the analysis of the conver gence behaviour\nof a semismooth Newton method for projection onto a spect rahedron\,\ni.e.\, the intersection of a linear manifold and the semidefin ite cone.\nIn this process\, we derive an explicit formula for the project ion onto\na face of the semidefinite cone obtained via regularization and\ nanalyze pathologies that arise in the absence of strict feasibility.\nWe further show that ill-conditioning of the Jacobian near optimality\ncharac terizes the degeneracy of the projection point. \\\\ \nAs an application\, we consider a simplified Wasserstein barycenter\nproblem\, a well-known N P-hard problem. We compute the Wasserstein\nbarycenter by exploiting the s tructure of the linear constraints to\nobtain a facially reduced doubly no nnegative (DNN) relaxation. This\nreduction provides a natural splitting f or applying the symmetric\nalternating direction method of multipliers (sA DMM). The resulting\nalgorithm exploits structure in the subproblems to co mpute strong\nupper and lower bounds. In most of the instances\, we achiev e the small\ngap between these bounds\, which means that the original prob lem is\nsolved. DTSTAMP:20260804T185614Z END:VEVENT BEGIN:VEVENT UID:6a7235cef07cf DTSTART;TZID=America/Toronto:20260807T113000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20260807T123000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/combopt-read inggroup-david-aleman-unsplittable-0 SUMMARY:CombOpt ReadingGroup - David Aleman-Unsplittable multicommodity flo ws\nin fully planar instances CLASS:PUBLIC DESCRIPTION:SPEAKER:\n\n David Aleman\n\nAFFILIATION:\n University of Water loo\n\nLOCATION:\n MC 6029\n\nABSTRACT: \n\nThe multicommodity flow probl em involves routing multiple distinct\ncommodities through a shared networ k. An instance is given by\nan _undirected _graph G=(V\, E(G) ) with ed ge capacities\, and a\ncollection of source-sink pairs (s_i\,t_i) in V wit h associated\nnonnegative demands d(s_i\, t_i). It will be convenient to t hink of the\nsource-sink pairs as forming the edges of a demand graph H=( V\, E(H)\n). A flow is _feasible_ if it routes all demands without excee ding\nthe edge capacities\, and it is _unsplittable_ if it routes each\n demand along a single path. Let C be the smallest value such that the\nexi stence of a feasible flow implies the existence of an unsplittable\nflow t hat exceeds the edge capacities by at most an additivie amount\nof C times the maximum demand value.  \nWe show that if G+H = (V\, E(G) U E(H) ) is planar\, then  1.5<= C <=\n2. \nJoint work with Kumar\, Poremba\, and Sh epherd.    DTSTAMP:20260804T185614Z END:VEVENT BEGIN:VEVENT UID:6a7235cef1389 DTSTART;TZID=America/Toronto:20260731T113000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20260731T123000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/combopt-read inggroup-sina-kalantarzadeh-minimum-bounded SUMMARY:CombOpt ReadingGroup - Sina Kalantarzadeh-Minimum Bounded Degree\nS panning Trees CLASS:PUBLIC DESCRIPTION:SPEAKER:\n\n Sina Kalantarzadeh\n\nAFFILIATION:\n University of Waterloo\n\nLOCATION:\n MC 6029\n\nABSTRACT: I will present Goemans’s beautiful\, though no longer\nstate-of-the-art\, 2006 result on the Minimu m Bounded-Degree Spanning\nTree problem. Given a weighted graph (G=(V\,E)) and degree bounds\n(B\\to\\mathbb{N})\, the goal is to find a minimum-cos t spanning tree (T)\nsatisfying (d_T(v)\\le B(v)) for every (v\\in V). Thi s problem is\nNP-hard. Fürer and Raghavachari (1992) gave a polynomial-ti me\nalgorithm for the unweighted setting that produces a spanning tree\nsa tisfying (d_T(v)\\le B(v)+1). For the weighted problem\, Goemans\ndesigned an elegant LP-rounding algorithm that returns a tree of cost\nat most tha t of the optimal degree-bounded solution while satisfying\n(d_T(v)\\le B(v )+2). I will explain this result and the simple yet\nbeautiful combinatori al optimization ideas underlying it. In 2007\,\nSingh and Lau improved the violation to (B(v)+1) using iterative\nrelaxation\, which I might give a talk about in later sessions. DTSTAMP:20260804T185614Z END:VEVENT BEGIN:VEVENT UID:6a7235cef1ce5 DTSTART;TZID=America/Toronto:20260805T140000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20260805T150000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/masters-thes is-presentation-martin-liu SUMMARY:Master's Thesis Presentation - Martin Liu CLASS:PUBLIC DESCRIPTION:SPEAKER:\n Martin Li\n\nSUPERVISOR(S):\n Vijay Bhattiprolu\n\nC OMITTEE:\n Jonathan Leake\, Levent Tuncel\n\nLOCATION:\n MC 6483\n\nABSTRA CT:\n\nThe $d$-dimensional Grothendieck constant is the smallest constant $K$\nsuch that \\begin{align*} \\sup\\left\\{\\sum_{i\,j=1}^n A_{ij}\\lang le\nu_i\,v_j\\rangle:u_i\,v_j\\in S^{d-1}\\right\\}\\le\nK\\cdot\\sup\\lef t\\{\\sum_{i\,j=1}^n\nA_{ij}x_iy_j:x_i\,y_j\\in\\{-1\,1\\}\\right\\} \\en d{align*}for any\n$n\\in\\mathbb{N}$ and any real $n\\times n$ matrix $A$. The inequality\nabove\, called the Grothendieck inequality\, has made a d eep impact in a\nvariety of areas such as functional analysis\, quantum in formation\ntheory\, and optimization. Determining the $d$-dimensional Grot hendieck\nconstant for any $d\\ge 3$ is a long-standing open problem.\n\nI n this paper\, we propose a worst operator in dimension 3\, whose\n$\\inft y\\to 1$ norm is conjectured to be $1/K_G(3)$. We study a related\nclass o f operators with nice geometric interpretations\, and we prove\nthe functi on $f:S^{d-1}\\to\\{-1\,1\\}$ corresponding to a hyperplane is\nuniquely o ptimal for this class\, with the isoperimetric inequality\nlying at the he art of our proof. DTSTAMP:20260804T185615Z END:VEVENT BEGIN:VEVENT UID:6a7235cef2a47 DTSTART;TZID=America/Toronto:20260804T120000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20260804T123000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/optimization -seminar-david-torregrosa-belen-convergence SUMMARY:Optimization seminar-David Torregrosa Belén-Convergence of a proxi mal\nstochastic subgradient method under the Kurdyka-Lojasiewicz condition CLASS:PUBLIC DESCRIPTION:SPEAKER:\n David Torregrosa Belén\n\nAFFILIATION:\n University of Alicante\n\nLOCATION:\n MC 5501\n\nABSTRACT:This talk presents a proxi mal stochastic subgradient\nmethod for minimizing the sum of an expected cost and a lower\nsemicontinuous\, prox-bounded function. We target a bro ad class of\nnonconvex integrands obeying a nonsmooth\, localized variant of the\ndescent lemma in the decision variable\, which in particular cov ers\nsmooth losses with Lipschitz gradient. At each iteration\, the\nexpe cted cost is replaced by a sample average that is progressively\nrefined\ , and the proximal stepsize is selected by an Armijo-type line\nsearch en forcing a\nsufficient decrease property up to stochastic errors induced by \nthe sample-based approximation. This framework accommodates more\ngener al problem formulations than existing methods and our analysis\nyields c onvergence guarantees that\, to the best of our knowledge\,\nare new even  in the smooth setting. Specifically\, we establish almost\nsure converg ence of the sequence of function values and stationarity\nof every accumu lation point of the trajectories under the relaxed\nrequirement that the sample-size sequence be merely nondecreasing and\nunbounded. Leveraging t he Kurdyka-Lojasiewicz property\, we further\nproof convergence of the wh ole trajectory to a single stationary\npoint. Finally\, for exponential-t ype desingularizing functions and\npolynomially growing sample sizes\, we derive explicit polynomial\nconvergence rates\, up to logarithmic factor \, for both the function\nvalues and the iterates. This is a joint work w ith Felipe Atenas\,\nPedro Pérez-Aros and Alejandro\nJofré\, from the Un iversity of Chile. DTSTAMP:20260804T185615Z END:VEVENT BEGIN:VEVENT UID:6a7235cef349a DTSTART;TZID=America/Toronto:20260804T113000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20260804T120000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/optimization -seminar-ting-kei-pong-conditional-gradient SUMMARY:Optimization seminar-Ting Kei Pong-A Conditional-Gradient-Based\nSi ngle-Loop Augmented Lagrangian Method for Inequality Constrained\nProblems CLASS:PUBLIC DESCRIPTION:SPEAKER:\n Ting Kei Pong\n\nAFFILIATION:\n The Hong Kong Polyte chnic University\n\nLOCATION:\n MC 5501\n\nABSTRACT:We consider the proble m of minimizing the sum of a Lipschitz\ndifferentiable convex function an d a proper closed convex function\nthat admits efficient linear minimiza tion oracles\, subject to\nmultiple smooth convex inequality constraint s. We adapt the\nclassical augmented Lagrangian (AL) method for these pr oblems: in\neach iteration\, our algorithm consists of one step of condit ional\ngradient (CG) method applied to the AL function\, followed by\nan  update of the dual variable as in classical AL methods with a\ndiminish ing dual stepsize. We study the convergence rate of our\nalgorithm under two standard stepsize rules for the CG method\,\nnamely\, an open-loop s tepsize and the short stepsize\, and obtain a\nrate that matches the bes t-known complexity for this class of\nproblems. We also establish accele rated rates when\nthe aforementioned proper closed convex function is the  indicator\nfunction of a uniformly convex set. This is a joint work wit h\nXiaozhou Wang and Zev Woodstock. DTSTAMP:20260804T185615Z END:VEVENT END:VCALENDAR