"""Claim 2 (Theorem 2 / Theorem 4): given a polynomial-time (alpha, gamma)- decomposition, the ICE algorithm achieves O(alpha) * rho(eta, .) + O(alpha * log^{-1}(gamma/(gamma-1)) * log k). Definition 1 (from the source): an (alpha,gamma)-decomposition is a pair (X_i, S_i) with Xhat = X_1 u ... u X_r such that for every i (A) |X_i| >= (|Xhat| - (|X_1|+...+|X_{i-1}|)) / 2 (B) if c(S_i) < 2 c(S_{i-1}) then 8 c(S_{i-1}) < c(S_{i+1}) (C) if c(S_i) > 10 c(S_{i-1}) then c(S_i) <= g(|Xhat|) * C_1, where C_1 is the min-cost solution covering ceil(|remaining|/2) elements of R_{i-1}. The decomposition oracle below is polynomial time: each S_i is built by the standard greedy partial-cover rule (cheapest set per newly covered element) until half of the remaining predicted elements are covered. C_1 is computed EXACTLY by ILP so that (C) is checked against the true optimum, not a proxy, and alpha is *measured* as c(S_i)/C_1 rather than assumed. ICE online phase: run a black-box online algorithm; track its spend; whenever cumulative online cost exceeds the cost of the next decomposition piece, buy it. """ import json, numpy as np from scipy.optimize import milp, LinearConstraint, Bounds from scipy.sparse import csc_matrix RES = {} def make_instance(m, n, rng, p=0.18): A = (rng.uniform(size=(m, n)) < p).astype(np.int8) for e in range(m): if A[e].sum() == 0: A[e, rng.integers(n)] = 1 cost = rng.uniform(1.0, 5.0, size=n) return A, cost def ilp_cover(A, cost, elems): """Exact min-cost cover of the given elements.""" if len(elems) == 0: return 0.0, np.zeros(A.shape[1], dtype=int) sub = A[list(elems)] c = LinearConstraint(csc_matrix(sub), lb=np.ones(len(elems)), ub=np.inf) r = milp(c=cost, constraints=[c], integrality=np.ones(A.shape[1]), bounds=Bounds(0, 1)) if not r.success: return None, None return float(r.fun), np.round(r.x).astype(int) def ilp_partial(A, cost, elems, need): """Exact min-cost solution covering at least `need` of `elems` (ILP with per-element indicators).""" elems = list(elems) if need <= 0: return 0.0 n = A.shape[1]; m = len(elems) # vars: n set-vars then m element-indicators sub = A[elems] rows, cols, vals = [], [], [] for i in range(m): # y_i <= sum_{S covering e_i} x_S for j in np.flatnonzero(sub[i]): rows.append(i); cols.append(j); vals.append(1.0) rows.append(i); cols.append(n+i); vals.append(-1.0) M = csc_matrix((vals, (rows, cols)), shape=(m, n+m)) cons = [LinearConstraint(M, lb=np.zeros(m), ub=np.inf)] sel = np.zeros((1, n+m)); sel[0, n:] = 1.0 cons.append(LinearConstraint(csc_matrix(sel), lb=need, ub=np.inf)) cvec = np.concatenate([cost, np.zeros(m)]) r = milp(c=cvec, constraints=cons, integrality=np.ones(n+m), bounds=Bounds(0, 1)) return float(r.fun) if r.success else None def greedy_partial(A, cost, remaining, need): """Polynomial-time oracle: greedy cheapest-per-new-element until `need` covered.""" rem = set(remaining); chosen = []; covered = set() while len(covered) < need: best, bj = None, None for j in range(A.shape[1]): new = len([e for e in rem if A[e, j] and e not in covered]) if new == 0: continue r = cost[j]/new if best is None or r < best: best, bj = r, j if bj is None: break chosen.append(bj) covered |= {e for e in rem if A[e, bj]} return chosen, covered def decompose(A, cost, Xhat): """Build (X_i, S_i) satisfying (A); measure alpha from (C) and gamma from the realised cost growth ratio.""" rem = list(Xhat); pieces = [] while rem: need = int(np.ceil(len(rem)/2)) S, cov = greedy_partial(A, cost, rem, need) Xi = sorted(cov & set(rem)) cS = float(cost[S].sum()) C1 = ilp_partial(A, cost, rem, need) pieces.append({"X_i": len(Xi), "cost_S_i": cS, "C1_exact": C1, "alpha_i": (cS/C1 if C1 and C1 > 0 else None), "propA": bool(len(Xi) >= need)}) rem = [e for e in rem if e not in cov] if not S: break return pieces def check_props(pieces): a = [p["alpha_i"] for p in pieces if p["alpha_i"] is not None] okA = all(p["propA"] for p in pieces) cs = [p["cost_S_i"] for p in pieces] okB = True for i in range(1, len(cs)-1): if cs[i] < 2*cs[i-1] and not (8*cs[i-1] < cs[i+1]): okB = False ratios = [cs[i]/cs[i-1] for i in range(1, len(cs)) if cs[i-1] > 0] return okA, okB, (max(a) if a else None), (max(ratios) if ratios else None) def online_greedy(A, cost, requests, bought): """Black-box online set cover: on an uncovered request, buy cheapest covering set.""" b = bought.copy(); spend = 0.0 for e in requests: if any(b[j] and A[e, j] for j in range(A.shape[1])): continue cand = np.flatnonzero(A[e]); j = cand[np.argmin(cost[cand])] b[j] = 1; spend += cost[j] return b, spend def ice(A, cost, requests, pieces_sets, piece_costs): """ICE: run the online algorithm; whenever its spend exceeds the next piece's cost, buy that piece too.""" bought = np.zeros(A.shape[1], dtype=int); spend = 0.0; k = 0 for e in requests: if not any(bought[j] and A[e, j] for j in range(A.shape[1])): cand = np.flatnonzero(A[e]); j = cand[np.argmin(cost[cand])] bought[j] = 1; spend += cost[j] while k < len(pieces_sets) and spend >= piece_costs[k]: for j in pieces_sets[k]: bought[j] = 1 spend += piece_costs[k]; k += 1 return bought, spend def run(): rows = [] for (m, n) in ((40, 60), (60, 90), (80, 120)): for corrupt in (0.0, 0.2, 0.5, 1.0): rng = np.random.default_rng(m*10+int(corrupt*10)) A, cost = make_instance(m, n, rng) req = list(rng.permutation(m)[:m//2]) optcost, _ = ilp_cover(A, cost, req) # prediction: corrupted version of the true request set Xhat = set(req) nswap = int(corrupt*len(req)) if nswap: drop = set(rng.choice(list(Xhat), size=min(nswap, len(Xhat)), replace=False)) Xhat -= drop pool = [e for e in range(m) if e not in req] Xhat |= set(rng.choice(pool, size=min(nswap, len(pool)), replace=False)) eta = min(len(req), len(set(req) ^ Xhat)) pieces = decompose(A, cost, sorted(Xhat)) okA, okB, amax, gmax = check_props(pieces) psets, pcosts = [], [] rem = sorted(Xhat) for p in pieces: need = int(np.ceil(len(rem)/2)) S, cov = greedy_partial(A, cost, rem, need) psets.append(S); pcosts.append(float(cost[S].sum())) rem = [e for e in rem if e not in cov] b_ice, _ = ice(A, cost, req, psets, pcosts) c_ice = float(cost[b_ice == 1].sum()) b_base, _ = online_greedy(A, cost, req, np.zeros(n, dtype=int)) c_base = float(cost[b_base == 1].sum()) rows.append({"m": m, "n": n, "corrupt": corrupt, "eta": eta, "OPT_ilp": round(optcost, 3), "ICE_cost": round(c_ice, 3), "baseline_cost": round(c_base, 3), "ICE_ratio": round(c_ice/optcost, 4), "baseline_ratio": round(c_base/optcost, 4), "pieces": len(pieces), "propA_holds": okA, "propB_holds": okB, "measured_alpha_max": (round(amax, 4) if amax else None), "max_cost_growth_gamma": (round(gmax, 3) if gmax else None)}) print(" m=%-3d corrupt=%.1f eta=%-3d OPT=%7.2f ICE=%7.2f (%.3f) base=%7.2f (%.3f) pieces=%d A=%s B=%s alpha<=%.2f" % (m, corrupt, eta, optcost, c_ice, c_ice/optcost, c_base, c_base/optcost, len(pieces), okA, okB, amax or -1), flush=True) RES["claim2_ice"] = { "rows": rows, "propA_all": all(r["propA_holds"] for r in rows), "propB_all": all(r["propB_holds"] for r in rows), "max_measured_alpha": max(r["measured_alpha_max"] for r in rows if r["measured_alpha_max"]), "ICE_beats_baseline_at_eta0": [r for r in rows if r["eta"] == 0], "n_cells": len(rows)} json.dump(RES, open("ice_results.json", "w"), indent=1) if __name__ == "__main__": run(); print("DONE")