A scaling-invariant algorithm for linear programming whose running time only depends on the constraint matrix
11:50 AM to 1:00 PM
Join Zoom Meeting https://columbiauniversity.zoom.us/j/94877990440?pwd=QWtWVGFBUTFTbHB2ak1mbmN3Mnd3QT09
Bento Natura, London School of Economics
Following the breakthrough work of Tardos (Oper. Res. '86) in the bit-complexity model, Vavasis and Ye (Math. Prog. '96) gave the first exact algorithm for linear programming in the real model of computation with running time depending only on the constraint matrix. For solving a linear programs (LP), Vavasis and Ye developed a primal-dual interior point method using a 'layered least squares' (LLS) step, and showed that O(n^{3.5} log (cond(A))) iterations suffice to solve (LP) exactly, where cond(A) is a condition measure controlling the size of solutions to linear systems related to the constraint matrix A.
Monteiro and Tsuchiya (SIAM J. Optim. '03), noting that the central path is invariant under rescalings of the columns of A, asked whether there exists an LP algorithm depending instead on the measure cond(A*), defined as the minimum cond(AD) value achievable by a column rescaling AD of A and gave strong evidence that this should be the case. We resolve this open question affirmatively.
In the first part of the talk we recall basic properties of interior point methods for linear programming.
Subsequently, we will introduce the so called 'circuit imbalance measure', a property of the kernel of A and utilize it together with standard tools from matroid theory to obtain a nearly-optimal rescaling of the constraint matrix in O(m^2 n^2 + n^3), that is: a rescaling A' of A such that log(cond(A')) is a constant factor approximation of log(cond(A*)).
In the second half of the talk we give an overview of the Vavasis and Ye algorithm, present the central ideas for the runtime analysis and
based on these ideas introduce our scaling-invariant LLS interior-point-method.
We will conclude with a more fine-grained runtime analysis, that is also applicable to Vavasis and Ye's algorithm to decrease the overall iteration complexity by a factor of n / log(n).
By that, we show that our algorithm has iteration complexity O(n^{2.5} log(n) log (cond(A*))).
This is joint work with Daniel Dadush, Sophie Huiberts and Laci Végh.
Add to GMail
LevelUp Your LinkedIn
3:00 PM to 4:00 PM
Online event
Do you want to know what makes your LinkedIn profile get noticed? Are you not sure what kind of things you should post on there?
Join CS@CU Tuesday, September 29th at 3:00 PM to hear from current and former Linkedin professionals (also Barnard alums!) to hear top tips to make your profile stand out!
Zoom registration required here - https://columbiauniversity.zoom.us/meeting/register/tJUpdO-hqT0jG9xoIMcgTv2QMjhGoGBUVoKv
Speakers:
Ankita Acharya, BC '19 Alum, Business Leadership Program Associate at LinkedIn
Keren Baruch, BC '13 Alum, Principal Product Manager at LinkedIn Marketing Solution
Email Ivy Elkins (ivy@cs.columbia.edu) for more details.
Career Center Connections: Maximize the Center for Career Education
4:00 PM to 5:00 PM
CCE Reps will speak with current undergrads about their services and how they support undergrad students.
Sarah Goldberg, Ph.D., Associate Director, Undergraduate Career Development at the Center for Career Education
Pete Bridge, M.Ed., Senior Associate Director, Employer and Alumni Relations at the Center for Career Education
Email Ivy Elkins (ivy@cs.columbia.edu) for more details.
CS@CU MS Bridge Info Session
3:00 PM to 4:00 PM
Online Event
Prof. Tony Dear
Join Zoom Meeting
https://columbiauniversity.zoom.us/j/95445102430
Meeting ID: 954 4510 2430
One tap mobile
+16468769923,,95445102430# US (New York)
+13017158592,,95445102430# US (Germantown)
Dial by your location
+1 646 876 9923 US (New York)
+1 301 715 8592 US (Germantown)
+1 312 626 6799 US (Chicago)
+1 669 900 6833 US (San Jose)
+1 253 215 8782 US (Tacoma)
+1 346 248 7799 US (Houston)
Meeting ID: 954 4510 2430
Find your local number: https://columbiauniversity.zoom.us/u/abU7zQUUuM
Join by SIP
95445102430@zoomcrc.com
Join by H.323
162.255.37.11 (US West)
162.255.36.11 (US East)
221.122.88.195 (China)
115.114.131.7 (India Mumbai)
115.114.115.7 (India Hyderabad)
213.19.144.110 (EMEA)
103.122.166.55 (Australia)
209.9.211.110 (Hong Kong SAR)
64.211.144.160 (Brazil)
69.174.57.160 (Canada)
207.226.132.110 (Japan)
Meeting ID: 954 4510 2430
CCE 2020 Virtual Micro Career Fair: Diversity
4:00 PM to 5:30 PM
https://columbia.joinhandshake.com/career_fairs/18207?ref=events-search
Are you looking for a more intimate recruiting event where you can meet employers interested in hiring diverse candidates?
Join us for networking and recruiting sessions with companies across a variety of industries. Representatives may be from companies within finance, arts, communications + media, consulting, tech, and more.
Whether you're just starting to explore careers or looking for your next opportunity, this is a great chance to connect with companies that have specific diversity recruiting pipelines as well as companies that are seeking to increase their recruitment of diverse students.
EVENT FORMAT:
Employers will be represented in a virtual career fair, hosted on Brazen. Students are encouraged to engage with as many employers as they like through the duration of the event.
** Please note the time for this event is tentative and subject to change. **
CS@CU MS Bridge Info Session
2:00 PM to 3:00 PM
Online Event
Prof. Tony Dear
Join Zoom Meeting
https://columbiauniversity.zoom.us/j/91105165256
Meeting ID: 911 0516 5256
One tap mobile
+16468769923,,91105165256# US (New York)
+13017158592,,91105165256# US (Germantown)
Dial by your location
+1 646 876 9923 US (New York)
+1 301 715 8592 US (Germantown)
+1 312 626 6799 US (Chicago)
+1 346 248 7799 US (Houston)
+1 669 900 6833 US (San Jose)
+1 253 215 8782 US (Tacoma)
Meeting ID: 911 0516 5256
Find your local number: https://columbiauniversity.zoom.us/u/aegS8k6m2s
Join by SIP
91105165256@zoomcrc.com
Join by H.323
162.255.37.11 (US West)
162.255.36.11 (US East)
221.122.88.195 (China)
115.114.131.7 (India Mumbai)
115.114.115.7 (India Hyderabad)
213.19.144.110 (EMEA)
103.122.166.55 (Australia)
209.9.211.110 (Hong Kong SAR)
64.211.144.160 (Brazil)
69.174.57.160 (Canada)
207.226.132.110 (Japan)
Meeting ID: 911 0516 5256
CS@CU MS Bridge Info Session
3:00 PM to 4:00 PM
Online Event
Prof. Tony Dear, https://www.cs.columbia.edu/ms-bridge/
Join Zoom Meeting
https://columbiauniversity.zoom.us/j/91307629351
Meeting ID: 913 0762 9351
One tap mobile
+16468769923,,91307629351# US (New York)
+13126266799,,91307629351# US (Chicago)
Dial by your location
+1 646 876 9923 US (New York)
+1 312 626 6799 US (Chicago)
+1 301 715 8592 US (Germantown)
+1 669 900 6833 US (San Jose)
+1 253 215 8782 US (Tacoma)
+1 346 248 7799 US (Houston)
Meeting ID: 913 0762 9351
Find your local number: https://columbiauniversity.zoom.us/u/abZsMh05wm
Join by SIP
91307629351@zoomcrc.com
Join by H.323
162.255.37.11 (US West)
162.255.36.11 (US East)
221.122.88.195 (China)
115.114.131.7 (India Mumbai)
115.114.115.7 (India Hyderabad)
213.19.144.110 (EMEA)
103.122.166.55 (Australia)
209.9.211.110 (Hong Kong SAR)
64.211.144.160 (Brazil)
69.174.57.160 (Canada)
207.226.132.110 (Japan)
Meeting ID: 913 0762 9351
Add to GMail