Home
Browse by Subject
eBooks
Current Leaflets
and Catalogs
Publishers
Conferences
Typesetting
and Pre-Press
About
sign up for special offers in your fields of interest  •  sign in to see what suggestions ISD has for you or to create a wishlist
70 Enterprise Drive, Suite 2
Bristol, CT 06010
USA
+1 860 584-6546
orders@isdistribution.com
quick search
or
advanced search
my account
email address
password
Who am I? And what's my password?
Sign in
or Create an Account
my shopping cart
is currently empty
view cart / check out
335 pages
8 x 5 inches
Logos Verlag Berlin
Language:
English
Paperback (November 2020)
ISBN-13 9783832552060
ISBN-10 3832552065
$81.00
In stock
add to wish list
Subjects:
IT and Computer Science
Mathematics
The Complexity of Zadeh's Pivot Rule
by Alexander Vincent Hopp
The Simplex algorithm is one of the most important algorithms in discrete optimization, and is the most used algorithm for solving linear programs in practice. In the last 50 years, several pivot rules for this algorithm have been proposed and studied. For most deterministic pivot rules, exponential lower bounds were found, while a probabilistic pivot rule exists that guarantees termination in expected subexponential time.

One deterministic pivot rule that is of special interest is Zadeh's pivot rule since it was the most promising candidate for a polynomial pivot rule for a long time. In 2011, Friedmann proved that this is not true by providing an example forcing the Simplex algorithm to perform at least a subexponential number of iterations in the worst case when using Zadeh's pivot rule. Still, it was not known whether Zadeh's pivot rule might achieve subexponential worst case running time.
Next to analyzing Friedmann's construction in detail, we develop the first exponential lower bound for Zadeh's pivot rule. This closes a long-standing open problem by ruling out this pivot rule as a candidate for a deterministic, subexponential pivot rule in several areas of linear optimization and game theory.
 
Add to wishlist
You currently have wishlists
Please click on the name of the wishlist you want to add the item to.
Add to Cart
  If you have received a leaflet or are ordering from a conference handlist and want to take advantage of a special
  reduced price, please enter the relevant promotional code.
 
  
  ISBN Title Price   Promotional Code  
    -  

          
Wishlist item added
The item has been successfully added to your selected wishlist.
Home • Top of Page • Contact • About ISD • Browse by Subject • Publishers • Typesetting & Pre-Press • Sitemap • Privacy Statement • Terms & Conditions © ISD 2012