{"id":"c4675606-9e33-4ca3-8b72-1c099341b31a","arxiv_id":"1908.10351","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A centralized Hungarian-algorithm relay selector and a distributed stable-matching relay selector are proposed for M2M networks that use WiFi and LTE simultaneously.","lead":"This paper proposes two relay-selection algorithms for dense machine-to-machine networks where devices use WiFi to talk to each other and LTE to reach the base station. One algorithm finds the best possible set of relays with a central coordinator, and the other lets devices choose relays locally with a stable matching method.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"ORSA optimality and MRSA's reported near-optimality hold only for a surrogate model with worst-case interference treated as fixed edge weights; the abstract's 1% and 3% claims are inconsistent, and the no-restriction MRSA variant is underspecified.","rationale":"The reader identified the fixed-weight surrogate assumption as the weakest assumption, and I agree: it is the most load-bearing concern because the word 'optimal' in the paper's title and claims attaches to the real relay selection problem, while the proof only covers the transformed bipartite matching with fixed weights. The paper itself acknowledges the worst-case interference simplification after Eq. (4), which flags rather than hides the gap, but it never quantifies the gap between the surrogate optimum and the true simultaneous-transmission optimum. This is not an internal inconsistency in the Hungarian/KAP construction (Theorem 1 is a standard transformation and is likely correct in its own terms -- though the proof sketch would benefit from a more careful statement of the bijection and of the Avalue threshold), but it is a correctness risk for the central claim, and the reader's CONDITIONAL verdict is appropriate. I also note two further manuscript-supported concerns that strengthen the conditional verdict. First, the paper's own numbers contradict: the abstract says MRSA is 'only about 1% lower than ORSA' while Section V-A says 'at most 3%' and the conclusion says 'about 3% higher than ORSA' (meaning ORSA is about 3% higher than MRSA). Second, Algorithm 2 is underspecified for the no-restriction scenarios described in Scenarios 1-3: the algorithm description assumes a quota-based acceptance procedure, but the paper never specifies how the base station's quota is handled when Q_BS = 100 and N_s varies, nor how a relay that is added to MATCHLIST handles its own next-hop selection in relation to its applicants; the pseudocode is only given for the initialization and step 1, and Step 2 is a separate short block, so the exact procedure for expanding the MATCHLIST with relays is not fully specified. These are addressable issues, not fatal, hence CONDITIONAL. The paper has independent value in the standard KAP-to-Hungarian reduction (which is a known technique) and in the stability proof, so I do not recommend REJECT or UNVERDICTED. My recommendation matches the reader's, with the same primary concern.","tokens_in":26010,"tokens_out":2267,"duration_ms":20118,"concrete_test":"Implement the full simulation in Section V (or ask for the C++ code) and compute, for a small instance (e.g., N_s = N_r = 10, Q_BS = 10), four quantities: (i) the optimal value of the fixed-weight kAP solved by ORSA; (ii) the value of the same matching when actual SINRs are recomputed after the assignment, with only the matched pairs transmitting on WiFi; (iii) the value of the matching that would be obtained by solving the assignment problem on weights recomputed after each pairing; (iv) MRSA's value with the same recomputed SINRs. If (i) and (ii) differ systematically, or (iii) differs from (i), then the claimed optimality applies only to the surrogate. Also rerun Scenario 1 with Q_BS = N_s = 100 to see whether the abstract's 'about 1%' or the text's 'at most 3%' is the correct figure for the MRSA/ORSA gap.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central claim, that ORSA optimally solves the relay selection problem and MRSA is within 1-3% of optimal, depends on a modeling assumption that is stated but not justified: edge weights are computed from equations (2)-(4) where the WiFi SINR of each source-relay link already includes interference from all other sources, and the LTE SINR in equation (3) has zero interference. Therefore each min(C_{s,r}, C_{r,BS}) is a fixed number independent of the matching. Under this fixed-weight, additive-capacity surrogate, the k-cardinality assignment transformation in Section III-B and Hungarian Algorithm 1 do yield an optimal matching for that surrogate; this part is internally sound. The load-bearing weak point is that the paper never shows that the optimal matching for the fixed-weight surrogate is optimal--or even feasible--for the actual network, where interference depends on which sources transmit simultaneously on the shared WiFi channel. The text after Eq. (4) explicitly adopts 'maximum probable interference... worst possible interference conditions,' so the proof of Theorem 1 and the claim 'ORSA provides an optimal solution for the relay selection problem' do not transfer to the real system. A second, independent issue: the abstract claims MRSA is 'only about 1% lower than ORSA' while Section V-A and the conclusion report 'at most 3%' and 'about 3%'; together with the fact that Algorithm 2 is never specified for the no-restriction scenario (the procedure assumes the recipient has a quota, but the scenario sets Q_BS = 100 with N_s up to 100, and relays have quota 1 while the base station's processing of requests is not fully detailed), the headline numerical claims are not reproducible from the text.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies uplink relay selection in a single-cell M2M network in which active sources may send data directly to the base station over LTE or via idle relays, using WiFi for the source-to-relay hop and LTE for the relay-to-base-station hop. The base station has QBS LTE channels, and the goal is to assign sources to next hops so as to maximize total capacity. The paper proposes ORSA, a centralized algorithm that transforms the relay selection problem into a k-cardinality assignment problem and solves it with the Hungarian algorithm after adding dummy vertices, and MRSA, a distributed algorithm based on deferred acceptance. It proves the optimality of the kAP solver, claims that ORSA is optimal for the relay selection problem, and claims that MRSA produces a stable and source-optimal stable matching. Simulations in four scenarios compare ORSA and MRSA with direct transmission (WRSA) and random relay selection (RRSA).","tokens_in":26331,"tokens_out":11021,"duration_ms":118240,"significance":"If the central optimality claim held for the actual network, ORSA would be a useful centralized benchmark with O((Ns+Nr)^3) complexity, and MRSA would be a practical distributed alternative with stability guarantees and near-optimal average capacity when the number of channels is unrestricted. The paper is careful to provide proofs for the kAP transformation and for the stability of the matching, and it reports 1000-run simulations against two baselines with standard deviations. However, the optimality proof applies to a fixed-weight surrogate model with worst-case interference, and the claimed 'new' kAP solver appears to reproduce the known Volgenant transformation. The contribution is plausible and potentially useful, but the central claims need to be either restricted to the model actually solved or validated against the coupled interference behavior of the real network.","major_comments":[{"comment":"In the transformation in Section III-B2 and Algorithm 1 Step 2, the number of vertices added to the right side is Ns - QBS, which is negative whenever QBS > Ns. This case occurs in Scenarios 1-3 whenever Ns < 100 and in Scenario 4 whenever Ns < QBS, i.e., exactly in the simulations used for the 'no restriction' claims. The construction therefore needs a k' = min(QBS, Ns) correction or a separate handling of the unrestricted case, and the simulations must state which corrected version was actually run.","section":"§III-B2, Algorithm 1 Step 2"},{"comment":"The optimality proof of Theorem 1 and the claim that ORSA 'provides an optimal solution for the relay selection problem' apply to a surrogate problem whose edge weights are fixed numbers. In Eq. (2), the WiFi SINR of every source-relay pair already contains interference from all other sources, regardless of which sources actually transmit on WiFi, and the text after Eq. (4) explicitly adopts 'maximum probable interference' and 'worst possible interference conditions.' In the actual network, the set of simultaneously transmitting WiFi sources is determined by the matching itself, so the optimal matching for the fixed-weight graph need not maximize, and may not even be optimal for, the true capacity objective. Please either restrict the optimality claim to the fixed-capacity model or add a validation against an exhaustive search or iterative SINR recomputation in a small network.","section":"§II (Eq. (2)-(4)), §III-B"},{"comment":"The manuscript claims a 'new solver' for the k-cardinality assignment problem, but the construction—add m-k dummy vertices to one side, n-k to the other, weight added-to-original edges with a large value, and solve the resulting standard assignment—is the same as the Volgenant transformation cited as [34]. The authors should either identify a substantive difference in construction, proof, or complexity, or revise the novelty claim and compare against [34] explicitly.","section":"§III-A, Main Contributions"},{"comment":"The quantitative near-optimality claim is internally inconsistent: the abstract states that MRSA is 'only about 1% lower' than ORSA, while Section V-A states 'at most 3% less' and the conclusion states 'about 3% higher'; no confidence intervals are given for either number. Please reconcile these statements and report the distribution or standard error of the ORSA-MRSA gap.","section":"Abstract; §V-A; §VI"}],"minor_comments":[{"comment":"The sentence 'the optimal allocation in ORSA has been able to increase the number of unmatched sources compared to MRSA' should read 'decrease'; ORSA has fewer unmatched sources, as Fig. 9 and the following sentence indicate.","section":"§V-A"},{"comment":"The condition '0≤ 0j MRSA > WRSA > RRSA) is consistent with what the algorithm should do.\n\nThe soft spots, in order of severity:\n\n1. Algorithm 1 is underspecified for exactly the no-restriction case. Step 2 says to add Ns-QBS right-side dummy vertices. When QBS > Ns—which is Scenario 1-3 with QBS=100 and Ns<100—that count is negative. The matrix construction also needs columns for Nr+QBS right-side vertices, but only has Ns+Nr columns, so it silently drops BS channels beyond Ns+Nr. It still works because those channels are identical, but the text never says so or gives a k' = min(QBS, Ns) correction. This must be fixed before the algorithm is reproducible.\n\n2. The optimality claim is for the fixed-weight surrogate. Because Eq. (2) includes interference from all other sources, each edge weight is constant before matching; the paper says it is simulating worst-case interference. So ORSA is optimal for that worst-case model. That is an explicitly stated simplification, not a hidden error, but the paper should state that optimality does not extend to a system where interference depends on which sources actually transmit.\n\n3. The abstract says MRSA is \"about 1% lower\" while the conclusion and Scenario 1 say \"about 3%\". One number is wrong. Also, no code or data is provided, so the simulation numbers cannot be independently checked.\n\nOverall: the central argument is sound for the model as defined. The paper deserves a serious referee, but needs a major revision to specify the unconstrained case, reconcile the numbers, and clarify the surrogate-model caveat. I'd send it to review, not desk-reject it.","headline":"Competent application of kAP + deferred acceptance to M2M dual-RF relay selection; the central optimality proof holds for the stated worst-case interference model, but Algorithm 1 is underspecified when QBS > Ns and the abstract/body capacity gap numbers disagree.","tokens_in":26900,"tokens_out":6567,"would_cite":false,"duration_ms":67185,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C27","05C70"],"pacs":[],"model":"deepseek-v4-flash","headline":"Optimal M2M relay selection reduces to a k-cardinality assignment problem solvable by the Hungarian algorithm, and a distributed stable-matching variant stays within a few percent of that optimum.","keywords":["relay selection","machine-to-machine communications","k-cardinality assignment problem","Hungarian algorithm","matching theory","deferred acceptance","stable matching","static RF interfaces"],"falsifier":"Re-run the ORSA assignment in a simulator that, after a matching is chosen, recomputes each link's SINR using only the sources and relays that actually transmit simultaneously instead of using all sources as interferers; if some feasible matching other than ORSA's yields a higher total capacity under those recomputed weights, then ORSA's optimality for the real objective is refuted.","tokens_in":25822,"feed_emoji":"📡","tokens_out":7407,"duration_ms":71372,"temperature":0.7,"pith_summary":"The paper's goal is to decide, for a dense machine-to-machine cell, which idle machines should relay each active source's data to the base station when the base station has a limited number of channels and every machine has two radio interfaces. It claims a centralized algorithm (ORSA) solves this selection exactly: the problem is recast as a k-cardinality assignment problem on a bipartite graph whose edge weights are precomputed two-hop capacities, and a transformation with dummy vertices and very large weights turns that into a standard assignment problem solved by the Hungarian algorithm, with a proof that optimal solutions correspond one-to-one. It also claims a decentralized algorithm (MRSA) built on deferred acceptance produces a stable matching, one that is optimal for sources among all stable matchings, and that in simulation MRSA's average capacity lands only about 1–3% below ORSA's when channel count is unrestricted. Because WiFi carries the source-relay links and LTE carries the base-station links in separate bands, the two hops do not interfere in the model, so capacities can be assigned before matching.","feed_headline":"Optimal relay selection reduces to an assignment problem","feed_subtitle":"A Hungarian-based central solver is provably exact; a distributed stable matching trails by 1–3%.","key_machinery":"The central object is the k-cardinality assignment problem (kAP): choose at most $k$ edges in a weighted bipartite graph to maximize total weight. The paper's machinery is a reduction from kAP to a standard assignment problem by adding dummy vertices and $A_{\\text{value}}$-weighted edges, then applying the Hungarian algorithm (the standard polynomial-time algorithm for maximum-weight perfect matching in a bipartite graph); a short proof shows optimal solutions correspond bijectively between the two problems. For MRSA, the machinery is the deferred acceptance procedure, with sources as proposers, relays holding quota 1, and the base station holding quota $Q_{BS}$; stability and source-optimality follow from the standard matching-theory arguments. The static RF-interface assumption (WiFi for M2M, LTE to the base station, different bands) is what keeps the two-hop and direct capacities from interfering with one another in the model, so the edge weights can be fixed in advance.","core_discovery":"At the center is the observation that if every candidate link's capacity is treated as a fixed number before assignment, then selecting relays and direct connections under a base-station quota $Q_{BS}$ is exactly a maximum-weight matching problem with at most $Q_{BS}$ edges. ORSA builds a bipartite graph with sources on one side and relays plus $Q_{BS}$ copies of the base-station channel on the other; edge weights are $\\min(C_{s,r}, C_{r,BS})$ for a two-hop path and $C_{s,BS}$ for direct access. To solve the k-cardinality assignment problem, the paper adds $(m-k)$ and $(n-k)$ dummy vertices on the two sides, assigns a very large weight $A_{\\text{value}}$ to edges touching the dummies, and argues through Lemma 1 and Theorem 1 that in any optimal perfect matching exactly $k$ original edges survive and exactly $(m-k)+(n-k)$ big-weight edges are taken, so the optimal solution transfers back. MRSA, in contrast, has sources propose to relays or to the base station in order of capacity; each relay keeps at most one source and the base station keeps $Q_{BS}$ sources, and the deferred-acceptance logic yields a stable matching that is optimal for the proposing side. The simulation section reports ORSA at the top of all compared algorithms and MRSA close behind. A numerical inconsistency between the abstract and the body should be noted: the abstract says MRSA beats direct and random selection by about 15% and 98%, while the introduction and conclusion report 56% and 117%.","pith_inferences":["The dummy-vertex transformation is a generic gadget: any 'choose at most k edges' bipartite allocation problem with capacity limits can be solved by the same reduction, so it may transfer beyond relay selection to other quota-constrained assignment tasks.","If the fixed-weight decoupling breaks in a real deployment, an alternating loop — compute capacities under worst-case interference, match with ORSA, recompute interference for the actually selected transmitters, re-match — would be a natural testable extension; the paper itself does not explore it.","The abstract/body discrepancy in the baseline gains (15%/98% vs 56%/117%) suggests that at least one of those sets of numbers needs verification before the quantitative claims are quoted externally."],"forward_implications":["ORSA gives an exact optimum for the modeled problem: among all assignments respecting the one-relay-per-source and $Q_{BS}$-channel constraints, no other feasible selection can have higher total capacity.","MRSA's matching is stable and, for every source, at least as good as any other stable matching achievable with the same players; in the simulated settings it stays within roughly 1–3% of ORSA's average capacity.","Because the two RF interfaces use separate bands, source-relay WiFi transmissions and LTE links to the base station can proceed simultaneously without cross-interface interference, which is what makes the static setting a capacity win.","The complexity figures matter for deployment: ORSA is $O((N_s+N_r)^3)$ centralized, MRSA is $O((N_s+N_r)^2)$ distributed, so the decentralized option scales better in dense cells.","Adding more relays improves both algorithms' average capacity and reduces unmatched sources, while reducing LTE channels increases per-source capacity until the number of sources passes the channel count."],"supporting_citations":[{"why":"Supplies the deferred acceptance procedure that MRSA is built on, giving stability and source-optimality.","marker":"[30]"},{"why":"Shows that k-cardinality assignment can be solved by transformation, the general approach ORSA's solver extends.","marker":"[34]"},{"why":"Defines the k-cardinality assignment problem and its standard formulation, which ORSA maps the relay selection problem onto.","marker":"[35]"},{"why":"Provides the Hungarian algorithm implementation and the $O(N^3)$ complexity bound that ORSA inherits.","marker":"[36]"},{"why":"Origin of the Hungarian method for the standard assignment problem that the transformed kAP is fed into.","marker":"[37]"},{"why":"Provides the two-hop decode-and-forward capacity expression $\\min(C_{s,r}, C_{r,BS})$ used as the relay edge weight.","marker":"[12]"},{"why":"Another source for the decode-and-forward two-hop capacity model used in the problem formulation.","marker":"[32]"}],"fun_headline_variants":["Relay selection solved as k-cardinality assignment problem","Optimal relay choice via Hungarian; matching is near-optimal","ORSA exact; MRSA trails by 1% in M2M relay selection","Relay selection: optimal via assignment, near-optimal via matching"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that each edge's capacity is a fixed number known before matching, computed under maximum-probable interference; in the real network, interference depends on which sources and relays actually transmit together, so the proof of ORSA's optimality applies to the surrogate fixed-weight graph rather than automatically to the live radio environment.","fun_headline_variants_meta":{"raw":{"variants":["Relay selection solved as k-cardinality assignment problem","Optimal relay choice via Hungarian; matching is near-optimal","ORSA exact; MRSA trails by 1% in M2M relay selection","Relay selection: optimal via assignment, near-optimal via matching"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000963,"raw_usage":{"total_tokens":4201,"prompt_tokens":1149,"completion_tokens":3052,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":765,"completion_tokens_details":{"reasoning_tokens":2976}},"tokens_in":765,"tokens_out":3052,"duration_ms":20216,"temperature":1.0,"reasoning_tokens":2976,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:13:14.396374+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Re-run the ORSA assignment in a simulator that, after a matching is chosen, recomputes each link's SINR using only the sources and relays that actually transmit simultaneously instead of using all sources as interferers; if some feasible matching other than ORSA's yields a higher total capacity under those recomputed weights, then ORSA's optimality for the real objective is refuted.","supporting_citations":[{"cited_title":"College Admissions and the Stability of Mar- riage,","cited_arxiv_id":null,"evidence_quote":"Supplies the deferred acceptance procedure that MRSA is built on, giving stability and source-optimality."},{"cited_title":"Solving the k-cardinality Assignment Problem by Trans- formation","cited_arxiv_id":null,"evidence_quote":"Shows that k-cardinality assignment can be solved by transformation, the general approach ORSA's solver extends."},{"cited_title":"The k-cardinality Assignment Problem","cited_arxiv_id":null,"evidence_quote":"Defines the k-cardinality assignment problem and its standard formulation, which ORSA maps the relay selection problem onto."},{"cited_title":"The Dynamic Hungarian Algorithm for the Assignment Problem with Changing Costs","cited_arxiv_id":null,"evidence_quote":"Provides the Hungarian algorithm implementation and the $O(N^3)$ complexity bound that ORSA inherits."},{"cited_title":"The Hungarian Method for the Assignment Problem","cited_arxiv_id":null,"evidence_quote":"Origin of the Hungarian method for the standard assignment problem that the transformed kAP is fed into."},{"cited_title":"Interference-Aware Relay Selection Scheme for Two-Hop Relay Networks with Multiple Source-Destination Pairs,","cited_arxiv_id":null,"evidence_quote":"Provides the two-hop decode-and-forward capacity expression $\\min(C_{s,r}, C_{r,BS})$ used as the relay edge weight."},{"cited_title":"Relay Selection and Power Allo- cation for Device-to-Device Communication Underlaying Heterogeneous Cellular Networks,","cited_arxiv_id":null,"evidence_quote":"Another source for the decode-and-forward two-hop capacity model used in the problem formulation."}],"review_version":1}