Home » Uncategorized » Linear Convergence for LP in small dimensions

Linear Convergence for LP in small dimensions

Raimund Seidel, Small-DImensional Linear Programming and Convex Hulls Made Easy, here. Raimund boxes out in pick up games and more importantly, he knows how to contact my old bball coach Herr Sturmi.

We present two randomized algorithms􏰇 One solves linear programs involv􏰀ing m constraints in d variables in exp ected time O 􏰈m􏰉􏰇 The other constructs convex hulls of n p oints in IRd 􏰌 d 􏰍 􏰊􏰌 in exp ected time O 􏰈nbd􏰎􏰅c 􏰉􏰇 In b oth b ounds d is considered to b e a constant􏰇 In the linear programming algorithm the dep endence of the time b ound on d is of the form d􏰋􏰇 The main virtue of our results lies in the utter simplicity of the algorithms as well as their analyses􏰇

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: