{"id":5744,"date":"2013-11-25T15:11:56","date_gmt":"2013-11-25T23:11:56","guid":{"rendered":"http:\/\/algnotes.info\/b\/?page_id=5744"},"modified":"2023-09-14T17:14:48","modified_gmt":"2023-09-15T01:14:48","slug":"contents","status":"publish","type":"page","link":"https:\/\/algnotes.info\/on\/","title":{"rendered":"<em> \u2014 table of contents \u2014 <\/em>"},"content":{"rendered":"<div class=\"latex-file\">\n<div class=\"latex-document\">\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<blockquote class=\"quote\"><p><center><em>Notes on topics related to algorithms<\/em><\/center><\/p><\/blockquote>\n<p><!--more--><\/p>\n<\/div>\n<\/div>\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div class=\"latex-section\">\n<ul class=\"list-pages-shortcode sibling-pages\"><li class=\"page_item page-item-5744\"><a href=\"https:\/\/algnotes.info\/on\/\"><em> \u2014 table of contents \u2014 <\/em><\/a><\/li>\n<li class=\"page_item page-item-8676 page_item_has_children\"><a href=\"https:\/\/algnotes.info\/on\/background\/\">Misc. background material<\/a>\n<ul class='children'>\n\t<li class=\"page_item page-item-901 page_item_has_children\"><a href=\"https:\/\/algnotes.info\/on\/background\/probabilistic-method\/\">Probabilistic method<\/a>\n\t<ul class='children'>\n\t\t<li class=\"page_item page-item-7215\"><a href=\"https:\/\/algnotes.info\/on\/background\/probabilistic-method\/basic-bounds\/\">basic bounds<\/a><\/li>\n\t\t<li class=\"page_item page-item-7217\"><a href=\"https:\/\/algnotes.info\/on\/background\/probabilistic-method\/examples\/\">examples (Max Cut, Tur\u00e1n\u2019s theorem)<\/a><\/li>\n\t\t<li class=\"page_item page-item-911\"><a href=\"https:\/\/algnotes.info\/on\/background\/probabilistic-method\/method-of-conditional-probabilities\/\">method of conditional probabilities (Max Cut)<\/a><\/li>\n\t\t<li class=\"page_item page-item-1270\"><a href=\"https:\/\/algnotes.info\/on\/background\/probabilistic-method\/pessimistic-estimators\/\">pessimistic estimators (Tur\u00e1ns theorem)<\/a><\/li>\n\t\t<li class=\"page_item page-item-1464\"><a href=\"https:\/\/algnotes.info\/on\/background\/probabilistic-method\/chernoff\/\">Chernoff bound<\/a><\/li>\n\t\t<li class=\"page_item page-item-3451\"><a href=\"https:\/\/algnotes.info\/on\/background\/probabilistic-method\/chernoff-proof\/\">Chernoff bound proof<\/a><\/li>\n\t<\/ul>\n<\/li>\n\t<li class=\"page_item page-item-5735 page_item_has_children\"><a href=\"https:\/\/algnotes.info\/on\/background\/stopping-times\/\">Bounds related to random stopping times<\/a>\n\t<ul class='children'>\n\t\t<li class=\"page_item page-item-1514\"><a href=\"https:\/\/algnotes.info\/on\/background\/stopping-times\/walds\/\">Wald\u2019s equation<\/a><\/li>\n\t\t<li class=\"page_item page-item-5630\"><a href=\"https:\/\/algnotes.info\/on\/background\/stopping-times\/walds-dependent\/\">Wald\u2019s equation for dependent increments<\/a><\/li>\n\t\t<li class=\"page_item page-item-5690\"><a href=\"https:\/\/algnotes.info\/on\/background\/stopping-times\/markov-for-supermartingales\/\">Markov bound for super-martingales<\/a><\/li>\n\t\t<li class=\"page_item page-item-3998\"><a href=\"https:\/\/algnotes.info\/on\/background\/stopping-times\/stopping-time-chernoff\/\">\u201cStopping-time\u201d Chernoff bounds<\/a><\/li>\n\t\t<li class=\"page_item page-item-5684\"><a href=\"https:\/\/algnotes.info\/on\/background\/stopping-times\/expected-maximum-sum\/\">Expected maximum (or minimum) of many sums<\/a><\/li>\n\t\t<li class=\"page_item page-item-5730\"><a href=\"https:\/\/algnotes.info\/on\/background\/stopping-times\/expected-deviation\/\">Expected deviation of a sum<\/a><\/li>\n\t<\/ul>\n<\/li>\n\t<li class=\"page_item page-item-1468 page_item_has_children\"><a href=\"https:\/\/algnotes.info\/on\/background\/linear-programming\/\">Linear programming<\/a>\n\t<ul class='children'>\n\t\t<li class=\"page_item page-item-815\"><a href=\"https:\/\/algnotes.info\/on\/background\/linear-programming\/modeling\/\">modeling Set Cover and Multicommodity Flow<\/a><\/li>\n\t\t<li class=\"page_item page-item-820\"><a href=\"https:\/\/algnotes.info\/on\/background\/linear-programming\/rounding\/\">rounding an LP relaxation<\/a><\/li>\n\t<\/ul>\n<\/li>\n\t<li class=\"page_item page-item-1102\"><a href=\"https:\/\/algnotes.info\/on\/background\/randomized-rounding\/\">Randomized rounding<\/a><\/li>\n\t<li class=\"page_item page-item-880\"><a href=\"https:\/\/algnotes.info\/on\/background\/greedy-example\/\">Set Cover \/ greedy algorithm<\/a><\/li>\n\t<li class=\"page_item page-item-1234\"><a href=\"https:\/\/algnotes.info\/on\/background\/set-cover-wolsey\/\">Set Cover \/ Wolsey\u2019s generalization<\/a><\/li>\n\t<li class=\"page_item page-item-932\"><a href=\"https:\/\/algnotes.info\/on\/background\/lagrangian-relaxation-example\/\">Lagrangian relaxation \/ example<\/a><\/li>\n\t<li class=\"page_item page-item-2145\"><a href=\"https:\/\/algnotes.info\/on\/background\/lagrangian-relaxation-discussion\/\">Lagrangian relaxation \/ discussion<\/a><\/li>\n<\/ul>\n<\/li>\n<li class=\"page_item page-item-8643 page_item_has_children\"><a href=\"https:\/\/algnotes.info\/on\/obliv\/\">Oblivious randomized rounding<\/a>\n<ul class='children'>\n\t<li class=\"page_item page-item-8640 page_item_has_children\"><a href=\"https:\/\/algnotes.info\/on\/obliv\/greedy\/\">Greedy examples<\/a>\n\t<ul class='children'>\n\t\t<li class=\"page_item page-item-8592\"><a href=\"https:\/\/algnotes.info\/on\/obliv\/greedy\/set-cover-unweighted\/\">Greedy Set Cover I: unweighted ln(n)-approximation<\/a><\/li>\n\t\t<li class=\"page_item page-item-8594\"><a href=\"https:\/\/algnotes.info\/on\/obliv\/greedy\/set-cover-weighted\/\">Greedy Set Cover II: weighted H(n)-approximation via random stopping time<\/a><\/li>\n\t\t<li class=\"page_item page-item-8590\"><a href=\"https:\/\/algnotes.info\/on\/obliv\/greedy\/set-cover-local\/\">Greedy Set Cover III: weighted H(d)-approximation via localizing<\/a><\/li>\n\t\t<li class=\"page_item page-item-8565\"><a href=\"https:\/\/algnotes.info\/on\/obliv\/greedy\/set-cover-alterations\/\">Set Cover \/ alterations<\/a><\/li>\n\t\t<li class=\"page_item page-item-8569\"><a href=\"https:\/\/algnotes.info\/on\/obliv\/greedy\/set-cover-markov\/\">Set Cover \/ using Markov to bound the cost<\/a><\/li>\n\t\t<li class=\"page_item page-item-8567\"><a href=\"https:\/\/algnotes.info\/on\/obliv\/greedy\/set-cover-grasp\/\">Set Cover \/ GRASP (greedy randomized search procedure; unweighted)<\/a><\/li>\n\t\t<li class=\"page_item page-item-8563\"><a href=\"https:\/\/algnotes.info\/on\/obliv\/greedy\/maximum-matching\/\">Maximum c-Matching \/ 2-approximation (local analysis; weighted)<\/a><\/li>\n\t\t<li class=\"page_item page-item-8571 page_item_has_children\"><a href=\"https:\/\/algnotes.info\/on\/obliv\/greedy\/set-multicover-unconstrained\/\">Unconstrained Set Multicover<\/a><\/li>\n\t<\/ul>\n<\/li>\n\t<li class=\"page_item page-item-8645 page_item_has_children\"><a href=\"https:\/\/algnotes.info\/on\/obliv\/lagrangian\/\">Lagrangian-relaxation examples<\/a>\n\t<ul class='children'>\n\t\t<li class=\"page_item page-item-8587\"><a href=\"https:\/\/algnotes.info\/on\/obliv\/lagrangian\/multicommodity-flow-slow\/\">Multicommodity Flow I: Lagrangian relaxation via Chernoff<\/a><\/li>\n\t\t<li class=\"page_item page-item-8582\"><a href=\"https:\/\/algnotes.info\/on\/obliv\/lagrangian\/multicommodity-flow-increments\/\">Multicommodity Flow II: width-independence via non-uniform increments<\/a><\/li>\n\t\t<li class=\"page_item page-item-8584\"><a href=\"https:\/\/algnotes.info\/on\/obliv\/lagrangian\/multicommodity-flow-local\/\">Multicommodity Flow III: better approximation via localization<\/a><\/li>\n\t\t<li class=\"page_item page-item-8602\"><a href=\"https:\/\/algnotes.info\/on\/obliv\/lagrangian\/sparse-strategies\/\">Sparse strategies for zero-sum matrix games<\/a><\/li>\n\t\t<li class=\"page_item page-item-8600\"><a href=\"https:\/\/algnotes.info\/on\/obliv\/lagrangian\/set-cover-unweighted-fractional\/\">Fractional Set Cover \/ unweighted<\/a><\/li>\n\t\t<li class=\"page_item page-item-8598\"><a href=\"https:\/\/algnotes.info\/on\/obliv\/lagrangian\/set-cover-fractional\/\">Fractional Set Cover<\/a><\/li>\n\t<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n<li class=\"page_item page-item-8384\"><a href=\"https:\/\/algnotes.info\/on\/plog\/\">Writing wordpress blog entries in laTeX with plog (plasTeX and blogpost)<\/a><\/li>\n<\/ul>\n<p>Navigate using the menubar at the top of the window, and the arrows at the left and right edges. <\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>Notes on topics related to algorithms<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":1,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-5744","page","type-page","status-publish","hentry"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/5744","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/comments?post=5744"}],"version-history":[{"count":0,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/5744\/revisions"}],"wp:attachment":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/media?parent=5744"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}