Difference between revisions of "Applied Algebra Seminar Spring 2020"

From UW-Math Wiki
Jump to: navigation, search
(23 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 +
'''When''':  11:00am, Thursdays
 +
 +
'''Where''':  901 Van Vleck Hall
 +
 +
'''List''':  mathaas@lists.wisc.edu, to join email join-mathaas@lists.wisc.edu
 +
 +
'''Contact''':  Shamgar Gurevich, Jose Rodriguez
 +
 +
 
== Spring 2020 Schedule ==
 
== Spring 2020 Schedule ==
  
Line 13: Line 22:
 
|-
 
|-
 
|February 27
 
|February 27
 +
|
 +
|
 +
|-
 +
|March 5
 +
|
 +
|
 +
|-
 +
|March 12
 +
|
 +
|
 +
|-
 +
|March 19
 +
|Spring Break
 +
|
 +
|-
 +
|March 26
 +
|
 +
|
 +
|-
 +
|April 2
 +
|
 +
|
 +
|-
 +
|April 9
 +
|
 +
|
 +
|-
 +
|April 16
 +
|
 +
|
 +
|-
 +
|April 23
 
|
 
|
 
|  
 
|  
Line 18: Line 59:
 
|}
 
|}
  
==Advertisements==
+
== Abstracts ==
 +
===Carla Michini===
 +
'''Short simplex paths in lattice polytopes
 +
'''
 +
 
 +
We consider the problem of optimizing a linear function over a lattice polytope P contained in [0,k]^n and defined via m linear inequalities. We design a simplex algorithm that, given an initial vertex, reaches an optimal vertex by tracing a path along the edges of P of length at most O(n^6 k log k). The length of this path is independent on m and is the best possible up to a polynomial function, since it is only polynomially far from the worst case diameter. The number of arithmetic operations needed to compute the next vertex in the path is polynomial in n, m and log k. If k is polynomially bounded by n and m, the algorithm runs in strongly polynomial time. This is a joint work with Alberto Del Pia.
  
 +
----
 +
== Other events to note ==
 
{| cellpadding="8"
 
{| cellpadding="8"
 
!align="left" | date
 
!align="left" | date
Line 29: Line 77:
 
|Joe Kileel (Princeton)
 
|Joe Kileel (Princeton)
 
|-
 
|-
|February 27
+
|February 10
|
+
|[https://www.math.wisc.edu/wiki/index.php/Colloquia#Cynthia_Vinzant_.28NCSU.29///  Talk: Matroids, log-concavity, and expanders ]
|  
+
|Cynthia Vinzant (NCSU)
 
|-
 
|-
 
|}
 
|}
 
+
----
== Abstracts ==
 
===Carla Michini===
 
'''Short simplex paths in lattice polytopes
 
'''
 
 
 
We consider the problem of optimizing a linear function over a lattice polytope P contained in [0,k]^n and defined via m linear inequalities. We design a simplex algorithm that, given an initial vertex, reaches an optimal vertex by tracing a path along the edges of P of length at most O(n^6 k log k). The length of this path is independent on m and is the best possible up to a polynomial function, since it is only polynomially far from the worst case diameter. The number of arithmetic operations needed to compute the next vertex in the path is polynomial in n, m and log k. If k is polynomially bounded by n and m, the algorithm runs in strongly polynomial time. This is a joint work with Alberto Del Pia.
 

Revision as of 18:23, 5 February 2020

When: 11:00am, Thursdays

Where: 901 Van Vleck Hall

List: mathaas@lists.wisc.edu, to join email join-mathaas@lists.wisc.edu

Contact: Shamgar Gurevich, Jose Rodriguez


Spring 2020 Schedule

date speaker title host(s)
February 20 Carla Michini (UW Madison) Short simplex paths in lattice polytopes Local
February 27
March 5
March 12
March 19 Spring Break
March 26
April 2
April 9
April 16
April 23

Abstracts

Carla Michini

Short simplex paths in lattice polytopes

We consider the problem of optimizing a linear function over a lattice polytope P contained in [0,k]^n and defined via m linear inequalities. We design a simplex algorithm that, given an initial vertex, reaches an optimal vertex by tracing a path along the edges of P of length at most O(n^6 k log k). The length of this path is independent on m and is the best possible up to a polynomial function, since it is only polynomially far from the worst case diameter. The number of arithmetic operations needed to compute the next vertex in the path is polynomial in n, m and log k. If k is polynomially bounded by n and m, the algorithm runs in strongly polynomial time. This is a joint work with Alberto Del Pia.


Other events to note

date event/title speaker
February 7 Talk: Inverse Problems, Imaging and Tensor Decomposition Joe Kileel (Princeton)
February 10 Talk: Matroids, log-concavity, and expanders Cynthia Vinzant (NCSU)