{"id":8563,"date":"2014-12-07T10:41:44","date_gmt":"2014-12-07T18:41:44","guid":{"rendered":"http:\/\/algnotes.info\/b\/?page_id=8563"},"modified":"2026-09-30T09:15:19","modified_gmt":"2026-09-30T17:15:19","slug":"maximum-matching","status":"publish","type":"page","link":"https:\/\/algnotes.info\/on\/obliv\/greedy\/maximum-matching\/","title":{"rendered":"Maximum c-Matching \/ 2-approximation (local analysis; weighted)"},"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>A 2-approximation for maximum weight <script type=\"math\/tex;\">c<\/script>-matching, illustrating localization.<\/em><\/center><\/p><\/blockquote>\n<p> \u00a0<!--more--><\/p>\n<p><div style=\"margin:0pt;padding:0pt;margin-bottom:12px\"><\/div>\n<\/p>\n<hr \/>\n<div class=\"expandable\" id=\"a0000000002\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\"Click for background material\u2026\" class=\"collapseomatic highlight\" tabindex=\"0\">Click for background material\u2026<\/summary>\n<div class=\"collapseomatic_content\">\n<ul class=\"itemize\">\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/obliv\">Using randomized rounding to derive greedy and Lagrangian-relaxation algorithms<\/a> <\/p>\n<\/li>\n<li>\n<p>Problem definition: <em>maximum <script type=\"math\/tex;\">c<\/script>-matching.<\/em> Given a graph <script type=\"math\/tex;\">G=(V,E)<\/script> with edge values <script type=\"math\/tex;\">v_e\\ge 0<\/script> and integer vertex capacities <script type=\"math\/tex;\">c_u\\gt 0<\/script>, a <em>fractional <script type=\"math\/tex;\">c<\/script>-matching<\/em> is a vector <script type=\"math\/tex;\">x\\in {\\mathbb R}_+^E<\/script> such that, for each vertex <script type=\"math\/tex;\">u\\in V<\/script>, <script type=\"math\/tex;\">x<\/script> meets the <em>capacity constraint<\/em> <script type=\"math\/tex;\">\\sum _{e\\ni u} x_e \\le c_u<\/script>. The value of the fractional matching is <script type=\"math\/tex;\">v\\cdot x = \\sum _e v_e x_e<\/script>. If <script type=\"math\/tex;\">x<\/script> has integer values, then <script type=\"math\/tex;\">x<\/script> is called a <em><script type=\"math\/tex;\">c<\/script>-matching<\/em>. <\/p>\n<\/li>\n<\/ul>\n<\/div>\n<\/details>\n<\/div>\n<hr \/>\n<\/p>\n<\/div>\n<\/div>\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div class=\"latex-section\">\n<h1 id=\"a0000000003\">Algorithm<\/h1>\n<div id=\"a0000000004\" class=\"my-theorem latex-paragraph latex-thm\">\n<div class=\"latex-paragraph-heading\">   <b \"=\"&quot;\">Theorem.<\/b>   <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p>The algorithm below is a 2-approximation algorithm. <\/p>\n<\/div><\/div>\n<table id=\"a0000000005\" class=\"latex-alg\" cellspacing=\"0\" cellpadding=\"4\" width=\"100%\" style=\"border-top:1px solid #CCC;border-bottom:1px solid #CCC;margin-top:2ex;margin-bottom:2ex;\">\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">&nbsp;<\/td>\n<td style=\"padding-left:0em\"><b style=\"font-size:90%\">input:<\/b> Graph <script type=\"math\/tex;\">G=(V,E)<\/script> with edge values <script type=\"math\/tex;\">v<\/script> and integer vertex capacities <script type=\"math\/tex;\">c<\/script><\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">&nbsp;<\/td>\n<td style=\"padding-left:0em\"><b style=\"font-size:90%\">output:<\/b> <script type=\"math\/tex;\">c<\/script>-matching <script type=\"math\/tex;\">\\tilde x<\/script><\/p>\n<div style=\"margin:0pt;padding:0pt;margin-bottom:12px\"><\/div>\n<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">1.<\/td>\n<td style=\"padding-left:0em\"> Initialize <script type=\"math\/tex;\">\\tilde x =\\mathbf0<\/script>. <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">2.<\/td>\n<td style=\"padding-left:0em\"> Repeat until every edge has an endpoint at capacity: <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">3.<\/td>\n<td style=\"padding-left:1em\"> Among edges with no such endpoint, choose <script type=\"math\/tex;\">e<\/script> maximizing <script type=\"math\/tex;\">v_e<\/script>; increment <script type=\"math\/tex;\">\\tilde x_e<\/script>.<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">4.<\/td>\n<td style=\"padding-left:0em\"> Return <script type=\"math\/tex;\">\\tilde x<\/script>. <\/td>\n<\/tr>\n<\/table>\n<div class=\"latex-paragraph\">\n<div class=\"latex-paragraph-heading\"> <b>Remark:<\/b> <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> This problem generalizes the LP dual of weighted Vertex Cover. The algorithm implicitly produces a 2-approximate (integer) solution for that problem. <\/p>\n<p>To prove the theorem we\u2019ll apply the method of conditional probabilities to the following rounding scheme: <\/p>\n<blockquote class=\"quote\"><p><em> Initialize <script type=\"math\/tex;\">\\tilde x =\\mathbf0<\/script>. Repeat until every edge has an endpoint at capacity: choose an edge <script type=\"math\/tex;\">e<\/script> from distribution <script type=\"math\/tex;\">x\/|x|<\/script> and increment <script type=\"math\/tex;\">\\tilde x_e<\/script> unless one of <script type=\"math\/tex;\">e<\/script>\u2019s endpoints is at capacity. Return <script type=\"math\/tex;\">\\tilde x<\/script>.<\/em> <\/p><\/blockquote>\n<\/div><\/div>\n<\/div><\/div>\n<\/div>\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div class=\"latex-section\">\n<h1 id=\"a0000000006\">A weak global analysis<\/h1>\n<p> We start with a weak \u201cglobal\u201d analysis of the rounding scheme. Let <script type=\"math\/tex;\">n<\/script> be the number of vertices. <\/p>\n<div id=\"a0000000007\" class=\"my-theorem latex-paragraph latex-lemma\">\n<div class=\"latex-paragraph-heading\">   <b>Lemma <\/b> (global analysis).  <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> The expected value of the <script type=\"math\/tex;\">c<\/script>-matching <script type=\"math\/tex;\">\\tilde x<\/script> is at least <script type=\"math\/tex;\">v\\cdot x\/n<\/script>. <\/p>\n<\/div><\/div>\n<div class=\"expandable\" id=\"a0000000008\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\"Click for proof of lemma\u2026\" class=\"collapseomatic highlight\" tabindex=\"0\">Click for proof of lemma\u2026<\/summary>\n<div class=\"collapseomatic_content\">\n<p> Let <script type=\"math\/tex;\">T<\/script> be the number of iterations until <script type=\"math\/tex;\">\\tilde x<\/script> makes some vertex constraint tight. <\/p>\n<p>Each of the first <script type=\"math\/tex;\">T<\/script> iterations contributes in expectation <script type=\"math\/tex;\">v\\cdot x\/|x|<\/script> to the value of <script type=\"math\/tex;\">\\tilde x<\/script>, so by Wald\u2019s equation the expectation of <script type=\"math\/tex;\">v\\cdot \\tilde x<\/script> is at least <script type=\"math\/tex;\">\\textrm{E}[T] v\\cdot x\/|x|<\/script>. <\/p>\n<p>To finish we show <script type=\"math\/tex;\">\\textrm{E}[T] \\ge |x|\/n<\/script>. Consider the sum of the vertex \u201cloads\u201d <script type=\"math\/tex;\">\\sum _{u\\in V} \\sum _{e\\ni u} \\tilde x_e\/c_u<\/script>. Using the feasibility of <script type=\"math\/tex;\">x<\/script>, in each iteration, the expected increase in the sum is <\/p>\n<div id=\"a0000000009\" class=\"equation\"><script type=\"math\/tex; mode=display\"> \\renewcommand{\\mathspread }{\\, \\, \\, }\\sum _u \\sum _{e\\ni u} \\frac{x_e\/|x|}{c_u} {\\, \\, \\, {\\le }\\, \\, \\, }\\sum _u \\frac{1}{|x|} {\\, \\, \\, {=}\\, \\, \\, }n\/|x|.  <\/script><\/div>\n<p> That is, the sum increases by at most <script type=\"math\/tex;\">n\/|x|<\/script> in expectation with each sample. The sum starts at zero and increases to at least 1 by time <script type=\"math\/tex;\">T<\/script>, so Wald\u2019s equation implies <script type=\"math\/tex;\">\\textrm{E}[T] \\ge |x|\/n<\/script>. <\/p>\n<\/div>\n<\/details>\n<\/div>\n<div class=\"latex-subsection\">\n<h2 id=\"a0000000010\">Localizing the analysis<\/h2>\n<p> We localize the analysis to improve the approximation ratio from <script type=\"math\/tex;\">1\/n<\/script> to <script type=\"math\/tex;\">1\/2<\/script>. <\/p>\n<div id=\"a0000000011\" class=\"my-theorem latex-paragraph latex-lemma\">\n<div class=\"latex-paragraph-heading\">   <b>Lemma <\/b> (local analysis).  <\/div>\n<div class=\"latex-paragraph-content inline-first-p\">\n<p> The expected value of the <script type=\"math\/tex;\">c<\/script>-matching is at least <script type=\"math\/tex;\">v\\cdot x\/2<\/script>. <\/p>\n<\/div><\/div>\n<p>To prove this lemma, for each edge <script type=\"math\/tex;\">e\\in E<\/script>, we apply the previous lemma to the \u201clocal\u201d subproblem for <script type=\"math\/tex;\">e<\/script> formed by <script type=\"math\/tex;\">e<\/script> and edges that share an endpoint with <script type=\"math\/tex;\">e<\/script>, and with modified objective function <script type=\"math\/tex;\">v'\\cdot x \\doteq x_e<\/script>. This gives <script type=\"math\/tex;\">\\textrm{E}[\\tilde x_e] \\ge x_e\/2<\/script>. Linearity of expectation then implies the desired result. <\/p>\n<div class=\"expandable\" id=\"a0000000012\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\"Click for proof of lemma\u2026\" class=\"collapseomatic highlight\" tabindex=\"0\">Click for proof of lemma\u2026<\/summary>\n<div class=\"collapseomatic_content\">\n<p> Fix any edge <script type=\"math\/tex;\">e\\in E<\/script>. Let <script type=\"math\/tex;\">T_e<\/script> be the number of iterations until <script type=\"math\/tex;\">\\tilde x<\/script> makes the vertex constraint tight for one of <script type=\"math\/tex;\">e<\/script>\u2019s endpoints. To show <script type=\"math\/tex;\">\\textrm{E}[T_e] \\ge |x|\/2<\/script>, consider the sum of <script type=\"math\/tex;\">e<\/script>\u2019s vertex loads, <script type=\"math\/tex;\">\\sum _{u\\in e} \\sum _{e'\\ni u} \\tilde x_{e'}\/c_u<\/script>. In each iteration, the expected increase in the sum is <\/p>\n<div id=\"a0000000013\" class=\"equation\"><script type=\"math\/tex; mode=display\"> \\renewcommand{\\mathspread }{\\, \\, \\, }\\sum _{u\\in e} \\sum _{e'\\ni u}\\frac{x_{e'}\/|x|}{c_u} {\\, \\, \\, {\\le }\\, \\, \\, }\\sum _{u\\in e} \\frac{1}{|x|} {\\, \\, \\, {=}\\, \\, \\, }\\frac{2}{|x|}.  <\/script><\/div>\n<p> The sum starts at zero and increases to at least 1 by time <script type=\"math\/tex;\">T<\/script>, so by Wald\u2019s equation, <script type=\"math\/tex;\">\\textrm{E}[T_e] \\ge |x|\/2<\/script>. <\/p>\n<p>Each of the first <script type=\"math\/tex;\">T_e<\/script> iterations contributes in expectation <script type=\"math\/tex;\">x_e\/|x|<\/script> to <script type=\"math\/tex;\">\\tilde x_e<\/script>, so by Wald\u2019s equation the expectation of <script type=\"math\/tex;\">\\tilde x_e<\/script> is at least <script type=\"math\/tex;\">\\textrm{E}[T_e] x_e\/|x| \\ge x_e\/2<\/script>. The lemma follows by linearity of expectation. <\/p>\n<\/div>\n<\/details>\n<\/div>\n<\/div>\n<\/div><\/div>\n<\/div>\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div class=\"latex-section\">\n<h1 id=\"a0000000014\">Method of conditional probabilities<\/h1>\n<p> Next we apply the method of conditional probabilities to the local analysis. <\/p>\n<p>As an exercise, the reader may wish to first try this for the global analysis: <\/p>\n<div class=\"expandable\" id=\"a0000000015\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\"Click for algorithm from global analysis\u2026\" class=\"collapseomatic highlight\" tabindex=\"0\">Click for algorithm from global analysis\u2026<\/summary>\n<div class=\"collapseomatic_content\">\n<table id=\"a0000000016\" class=\"latex-alg\" cellspacing=\"0\" cellpadding=\"4\" width=\"100%\" style=\"border-top:1px solid #CCC;border-bottom:1px solid #CCC;margin-top:2ex;margin-bottom:2ex;\">\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">1.<\/td>\n<td style=\"padding-left:0em\"> Initialize <script type=\"math\/tex;\">\\tilde x = \\mathbf0<\/script>. <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">2.<\/td>\n<td style=\"padding-left:0em\"> Repeat until a vertex is at capacity: <\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">3.<\/td>\n<td style=\"padding-left:1em\"> Choose an edge <script type=\"math\/tex;\">e=(u,w) \\in E<\/script> maximizing <script type=\"math\/tex;\">v_e \/ (d_u\/c_u + d_w\/c_w)<\/script>; increment <script type=\"math\/tex;\">\\tilde x_e<\/script>. Here <script type=\"math\/tex;\">d_u<\/script> is the degree of <script type=\"math\/tex;\">u<\/script>.<\/td>\n<\/tr>\n<tr>\n<td valign=\"top\" style=\"line-height:1.2em\">4.<\/td>\n<td style=\"padding-left:0em\"> Return <script type=\"math\/tex;\">\\tilde x<\/script> <\/td>\n<\/tr>\n<\/table>\n<p><b class=\"bf\">Hint:<\/b> Use <script type=\"math\/tex;\">\\renewcommand{\\mathspread }{\\, \\, \\, }v\\cdot {\\tilde x} + ({v\\cdot x}\/{n})\\big(1 - \\sum _{u\\in V}\\sum _{e\\ni u} {\\tilde x}_e\/c_u\\big) <\/script> for the pessimistic estimator for the conditional expectation of the final value of <script type=\"math\/tex;\">v\\cdot {\\tilde x}<\/script> given the current <script type=\"math\/tex;\">{\\tilde x}<\/script>. Argue that the algorithm keeps the pessimistic estimator from decreasing. <\/p>\n<\/div>\n<\/details>\n<\/div>\n<\/div><\/div>\n<\/div>\n<div class=\"latex-outer-sheet\">\n<div class=\"latex-inner-sheet\">\n<div class=\"latex-section\">\n<h1 id=\"a0000000017\">Algorithm<\/h1>\n<p>Finally, we show that applying the method of conditional probabilities yields the algorithm. <\/p>\n<div class=\"expandable\" id=\"a0000000018\" tabindex=\"10\">\n<details class=\"collapseomatic_details\">\n<summary title=\"Click for proof of theorem\u2026\" class=\"collapseomatic highlight\" tabindex=\"0\">Click for proof of theorem\u2026<\/summary>\n<div class=\"collapseomatic_content\">\n<p> Condition on the first <script type=\"math\/tex;\">t<\/script> random samples. We need a pessimistic estimator lower-bounding the conditional expectation of the value of the final <script type=\"math\/tex;\">c<\/script>-matching. <\/p>\n<p>Following the localized analysis, fix any edge <script type=\"math\/tex;\">e<\/script> and let <script type=\"math\/tex;\">T_e<\/script> denote the number of samples until one of <script type=\"math\/tex;\">e<\/script>\u2019s vertices reaches capacity. Given the current <script type=\"math\/tex;\">\\tilde x<\/script>, recall that the sum of <script type=\"math\/tex;\">e<\/script>\u2019s vertex loads is <\/p>\n<div id=\"a0000000019\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\phi ^t_e~ =~  \\sum _{u\\in e} \\sum _{e'\\ni u} \\frac{\\tilde x_{e'}}{c_u}.  <\/script><\/div>\n<p> Recall that in expectation, this sum increases by at most <script type=\"math\/tex;\">2\/|x|<\/script> with each sample, and that the sum is at least 1 at time <script type=\"math\/tex;\">T_e<\/script> (when one of <script type=\"math\/tex;\">e<\/script>\u2019s vertices is at capacity). So, by Wald\u2019s equation, the expected number of additional samples until one of <script type=\"math\/tex;\">e<\/script>\u2019s vertices reaches capacity is at least <script type=\"math\/tex;\">(1-\\phi _t)|x|\/2<\/script>. Until that happens, each sample has a chance of <script type=\"math\/tex;\">x_e\/|x|<\/script> of choosing <script type=\"math\/tex;\">e<\/script>. By Wald\u2019s equation, the expected further increase in <script type=\"math\/tex;\">v_e \\tilde x_e<\/script> is therefore at least <script type=\"math\/tex;\">v_e x_e(1-\\phi _e^t)\/2<\/script>. <\/p>\n<p>Let <script type=\"math\/tex;\">\\tilde E<\/script> denote the edges whose endpoints are both not yet at capacity. Summing over these edges, the expectation of the value of the final matching, given the current matching <script type=\"math\/tex;\">\\tilde x<\/script>, is at least <\/p>\n<div id=\"a0000000020\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\Phi _t ~ =~  \\renewcommand{\\mathspread }{\\, \\, \\, }v\\cdot \\tilde x ~ +~  \\sum _{e\\in \\tilde E} \\frac{v_e \\tilde x_e}{2} (1-\\phi ^t_e).  <\/script><\/div>\n<p> If the algorithm next increments <script type=\"math\/tex;\">\\tilde x_{\\tilde e}<\/script> for a given edge <script type=\"math\/tex;\">\\tilde e\\in \\tilde E<\/script>, this increases the vertex load of each vertex <script type=\"math\/tex;\">u \\in \\tilde e<\/script> by <script type=\"math\/tex;\">1\/c_{u}<\/script>. For each edge <script type=\"math\/tex;\">e\\in \\tilde E<\/script> incident to <script type=\"math\/tex;\">u<\/script>, this also decreases the sum <script type=\"math\/tex;\">\\phi _e^t<\/script> by <script type=\"math\/tex;\">1\/c_{u}<\/script>. Thus, letting <script type=\"math\/tex;\">\\tilde E(u)<\/script> denote the edges in <script type=\"math\/tex;\">\\tilde E<\/script> incident to <script type=\"math\/tex;\">u<\/script>, the increase in the pessimistic estimator is <\/p>\n<div id=\"a0000000021\" class=\"equation\"><script type=\"math\/tex; mode=display\">  \\Phi _{t+1}-\\Phi _t ~ \\ge ~  v_{\\tilde e} - \\frac{1}{2}\\sum _{u\\in \\tilde e} \\sum _{e\\in \\tilde E(u)} \\frac{x_e v_e}{c_u}.  <\/script><\/div>\n<p> (Note that edges may drop out of <script type=\"math\/tex;\">\\tilde E<\/script>, but this only increases the pessimistic estimator, as <script type=\"math\/tex;\">\\phi ^t_e \\ge 1<\/script> for such edges.) Since the algorithm chooses <script type=\"math\/tex;\">\\tilde e<\/script> to maximize <script type=\"math\/tex;\">v_e<\/script> among <script type=\"math\/tex;\">e\\in \\tilde E<\/script>, the right-hand side above is at least <\/p>\n<div id=\"a0000000022\" class=\"equation\"><script type=\"math\/tex; mode=display\">  v_{\\tilde e} - \\frac{v_{\\tilde e}}{2} \\sum _{u\\in \\tilde e} \\sum _{e\\in \\tilde E(u)} \\frac{x_e}{c_u} ~ \\ge ~  v_{\\tilde e} - \\frac{v_{\\tilde e}}{2} \\sum _{u\\in \\tilde e} 1 ~ =~  0.  <\/script><\/div>\n<p> (The inequality above follows from the feasibility of <script type=\"math\/tex;\">x<\/script>, in particular <script type=\"math\/tex;\">\\sum _{e\\ni u} x_e \\le c_u<\/script>.) <\/p>\n<p>Thus, the algorithm keeps the pessimistic estimator <script type=\"math\/tex;\">\\Phi _t<\/script> above <script type=\"math\/tex;\">v\\cdot x\/2<\/script>. Finally, at termination, note that <script type=\"math\/tex;\">v\\cdot \\tilde x = \\Phi _T<\/script>, because <script type=\"math\/tex;\">\\tilde E = \\emptyset <\/script>. <\/p>\n<\/div>\n<\/details>\n<\/div>\n<div class=\"latex-subsection\">\n<h2 id=\"a0000000023\">Related<\/h2>\n<ul class=\"itemize\">\n<li>\n<p><a href=\"http:\/\/algnotes.info\/on\/set-cover-local\"><script type=\"math\/tex;\">{\\rm H}(d)<\/script>-approximation ratio for Set Cover (localized)<\/a> <\/p>\n<\/li>\n<\/ul>\n<\/div>\n<\/div><\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>A 2-approximation for maximum weight -matching, illustrating localization. \u00a0<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":8640,"menu_order":7,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-8563","page","type-page","status-publish","hentry"],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8563","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=8563"}],"version-history":[{"count":0,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8563\/revisions"}],"up":[{"embeddable":true,"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/pages\/8640"}],"wp:attachment":[{"href":"https:\/\/algnotes.info\/on\/wp-json\/wp\/v2\/media?parent=8563"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}