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:6a6d796c3cd98 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 SUMMARY:Tutte Colloquium -Michael Friedlander- CLASS:PUBLIC DESCRIPTION:SPEAKER:\n Michael Friedlander\n\nAFFILIATION:\n University of British Columbia.\n\nLOCATION:\n MC 5501\n\nABSTRACT: TBA DTSTAMP:20260801T044324Z END:VEVENT BEGIN:VEVENT UID:6a6d796c3dc71 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:20260801T044324Z END:VEVENT BEGIN:VEVENT UID:6a6d796c3ea46 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:20260801T044324Z END:VEVENT BEGIN:VEVENT UID:6a6d796c3f68a 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:20260801T044324Z END:VEVENT BEGIN:VEVENT UID:6a6d796c402ee 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:20260801T044324Z END:VEVENT BEGIN:VEVENT UID:6a6d796c40e6b DTSTART;TZID=America/Toronto:20260730T143000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20260730T153000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/algebraic-an d-enumerative-combinatorics-seminar-maryam-yekta SUMMARY:Algebraic and Enumerative combinatorics seminar -Maryam Yekta-New\n bounds for integer flows and Verma modules via denormalized Lorentzian\nLa urent series CLASS:PUBLIC DESCRIPTION:SPEAKER:\n Maryam Yekta\n\nAFFILIATION:\n University of Waterlo o\n\nLOCATION:\n MC 5479\n\nABSTRACT: The theory of log concave polynomia ls has recently been\ndeveloped to study objects and problems in combinato rics and other\nsubfields in mathematics. Particular classes of log concav e\npolynomials called Lorentzian polynomials and denormalized and dually\n Lorentzian polynomials have been used to prove log concavity\nstatements f or various combinatorial sequences. This includes the\nstrongest form of M ason's log concavity conjecture on the independent\nsets of matroids and t he log concavity of sequences of Kostka numbers.\nIn this talk\, we develo p an analogous class of power series called\ndenormalized Lorentzian (DL) Laurent series. This class is the natural\ngeneralization of DL polynomial s to homogeneous power series with the\nbenefit of capturing a number of c ombinatorial generating series\nincluding the Kostant partition function f or integer flows of directed\ngraphs. We then analyze specific DL Laurent series to obtain new\nbounds for integral flows on general directed acycli c graphs and new\nbounds for the dimensions of weight spaces of parabolic\ n𝔰𝔩ₙ₊₁(ℂ) Verma modules.\n\nTHERE WILL BE A PRE-SEMINAR PRES ENTING RELEVANT BACKGROUND AT\nBEGINNING GRADUATE LEVEL STARTING AT 1:30PM IN MC 5417. DTSTAMP:20260801T044324Z END:VEVENT BEGIN:VEVENT UID:6a6d796c41a77 DTSTART;TZID=America/Toronto:20260731T153000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20260731T163000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/tutte-colloq uium-kanstantsin-pashkovich-simple-and-almost SUMMARY:Tutte Colloquium -Kanstantsin Pashkovich-Simple and Almost\nNon-Ada ptive 1/2-Approximation for Matroid Prophet Inequalities CLASS:PUBLIC DESCRIPTION:SPEAKER:\n Kanstantsin Pashkovich\n\nAFFILIATION:\n University of Waterloo\n\nLOCATION:\n MC 5501\n\nABSTRACT: Prophet inequalities are a fundamental model for online\ndecision-making under uncertainty. For mat roid constraints\, Kleinberg\nand Weinberg gave a tight 1/2-approximation\ , but their algorithm uses\nadaptive thresholds that depend on the previou sly accepted elements.\nSpecifically\, the mechanism of Kleinberg and Wein berg accepts an\narriving element if and only if it is feasible to add wit h respect to\nthe matroid constraint and the value of the arriving element passes\nits threshold\; but this threshold depends on the elements accept ed so\nfar and on the arriving element itself. Later\, Feldman\, Svensson\ , and\nZenklusen showed that one can give a 1/4-approximation for general\ nmatroids. Their algorithm is almost non-adaptive\, i.e.\, it uses\nnon-ad aptive thresholds but changes the underlying matroid to another\n``stricte r'' matroid. Feldman\, Svensson\, and Zenklusen also showed\nthat no const ant approximation is possible in general matroids using\nnon-adaptive thre sholds if one does not change the underlying matroid.\n\nWe give a new alm ost non-adaptive algorithm for matroid prophet\ninequalities that achieves a 1/2 guarantee. We change the underlying\nmatroid to a ``stricter'' new matroid that is a direct sum of several\nmatroids. For each part of the ne w matroid\, we precompute a single\nnon-adaptive threshold. Once the eleme nts start to arrive\, we accept\nan arriving element as long as it is feas ible with respect to the new\n``stricter'' matroid and its value passes th e precomputed threshold.\nIn addition\, we guarantee that our algorithm ac hieves the 1/2\nguarantee not simply with respect to the prophet's expecte d gain\, but\nwith respect to the stronger ex-ante relaxation value. \nThu s\, we provide the first almost non-adaptive algorithm for the\nmatroid pr ophet inequality that achieves the best-possible\napproximation guarantee of 1/2. If time permits\, we will also discuss\nhow we used LLM in this pr oject. DTSTAMP:20260801T044324Z END:VEVENT BEGIN:VEVENT UID:6a6d796c42652 DTSTART;TZID=America/Toronto:20260724T113000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20260724T123000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/combopt-read inggroup-mahtab-alghasi-local-dyadic-conjecture SUMMARY:CombOpt ReadingGroup -Mahtab Alghasi-The Local Dyadic Conjecture CLASS:PUBLIC DESCRIPTION:SPEAKER:\n\n Mahtab Alghasi\n\nAFFILIATION:\n University of Wat erloo\n\nLOCATION:\n MC 6029\n\nABSTRACT: A family of sets $\\mathcal{C}$ over a finite ground set\n$E(\\mathcal{C})$ is a clutter if no member of $\\mathcal{C}$ properly\ncontains another. A clutter is ideal if its cover ing polyhedron is\nintegral. A rational number whose denominator is a powe r of two is\ncalled \\emph{dyadic}.\n\nA longstanding conjecture of Paul S eymour\, known as the Dyadic\nConjecture\, predicts that\, for every ideal clutter\, the dual of the\nset covering linear program admits an optimal solution in which all\nvariables take dyadic values. We present a local ve rsion of this\nconjecture and provide evidence for it by proving the propo sed local\nstatement for binary clutters under certain assumptions. \nThis is joint work with Bertrand Guenin and Levent Tuncel. DTSTAMP:20260801T044324Z END:VEVENT BEGIN:VEVENT UID:6a6d796c42d57 DTSTART;TZID=America/Toronto:20260717T113000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20260717T123000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/combopt-read inggroup-noah-weninger-improved-algorithms SUMMARY:CombOpt ReadingGroup - Noah Weninger-Improved algorithms for\nshort est-path network interdiction CLASS:PUBLIC DESCRIPTION:SPEAKER:\n Noah Weninger\n\nAFFILIATION:\n University of Waterl oo\n\nLOCATION:\n MC 5029\n\nABSTRACT: \n\nIn the shortest-path network i nterdiction problem\, the objective is to\nselect a set $X$ of arcs in a d irected graph $G=(V\,A)$\, subject to a\nknapsack constraint on $X$\, such that the shortest $s$-$t$ path length\nin $(V\,A\\setminus X)$ is maximiz ed. We present an improved version of\nthe classic Israeli-Wood Benders co vering decomposition (2002). Our\nmethod is based on new upper and lower b ounds for the problem which\nintegrate cleanly into the Benders decomposit ion\, causing many\niterations to be skipped. Using similar techniques\, w e also derive new\ncovering heuristics\, which further reduce the running time. In\ncomputational experiments\, our improved algorithm achieves spee dups of\nup to two orders of magnitude. The speedup is most notable on the more\ndifficult large\, dense graphs: we can often solve instances on\nco mplete graphs with 1000 vertices and uniformly distributed weights\nand co sts within a few minutes. \nThis is joint work with Amir Dadpour and Ricar do Fukasawa. DTSTAMP:20260801T044324Z END:VEVENT BEGIN:VEVENT UID:6a6d796c438ca DTSTART;TZID=America/Toronto:20260724T153000 SEQUENCE:0 TRANSP:TRANSPARENT DTEND;TZID=America/Toronto:20260724T163000 URL:https://uwaterloo.ca/combinatorics-and-optimization/events/tutte-colloq uium-francisco-j-aragon-artacho-graph-based SUMMARY:Tutte Colloquium -Francisco J. Aragón Artacho-Graph-based splittin g\nalgorithms for optimization and feasibility problems CLASS:PUBLIC DESCRIPTION:SPEAKER:\n Francisco J. Aragón Artacho\n\nAFFILIATION:\n Unive rsity of Alicante\n\nLOCATION:\n MC 5501\n\nABSTRACT: When an optimizatio n problem is structured\, it is normally\nadvantageous to use this feature when designing algorithms to solve\nit. Following the divide-and-conquer paradigm\, splitting algorithms\niteratively solve simpler problems that a re defined by separately\nusing some parts of the original problem. In thi s talk\, we will recall\nsome classical methods and present some recent ad vances in this\nsubject\, paying special attention to splitting methods de vised by\ngraphs. DTSTAMP:20260801T044324Z END:VEVENT END:VCALENDAR