# Anonymous 2026 - Fairness k-submodular maximization subject to matroid constraint

## One-paragraph Summary

Day la paper fairness-matroid cho `k`-submodular maximization, mo rong ro ret so voi paper fairness 2024 chi co total budget. Paper xu ly ca monotone lan non-monotone objectives, nhung danh doi bang cach no khong giu lower bounds chinh xac trong guarantee cuoi: output chi duoc dam bao `floor(l_i / 2) <= |X_i| <= u_i`. Khung hai tang cua paper la:

- `UFairkSub`: giai upper-bound-only fairness duoi matroid;
- `FairkSub`: dung `UFairkSub` nhu subroutine, random split mot backbone lower-bound, roi mo rong thanh nghiem fairness-relaxed.

No la paper dau tien trong repo noi fairness `k`-submodular voi matroid va non-monotone.

## Classification Rationale

Paper thuoc `k-submodular` va nam trong nhanh fairness. Vi rang buoc chinh la matroid + fairness lower/upper bounds, no rat khac voi size / budget papers thong thuong. No la doi trong tu nhien cua Zhu et al. 2024: mot ben exact fairness duoi total budget, mot ben relaxed fairness duoi matroid.

## Setup

- Objective: non-negative `k`-submodular maximization, cho ca monotone va non-monotone.
- Fairness: moi nhan `i` co lower bound `l_i` va upper bound `u_i`.
- Feasibility: support tong thuoc mot matroid `M`.
- Paper tach thanh:
  - `UFkSM`: chi upper bounds;
  - `FkSM`: ca lower va upper bounds.

## Main Results

1. `UFairkSub` cho `UFkSM` dat:
   - monotone: xap xi `1 / 4.582 - epsilon`;
   - non-monotone: xap xi `1 / 6.494 - epsilon`;
   - query complexity `O((nk / epsilon) log r) + Q(Alg(SMM))`.
2. `FairkSub` cho `FkSM` tra ve nghiem thoa:
   - `supp(s) in M`;
   - `floor(l_i / 2) <= |X_i| <= u_i`.
3. Approximation cua `FairkSub`:
   - monotone: `1 / 9.164 - epsilon / 2`;
   - non-monotone: `1 / 25.976 - epsilon / 4`.

## Core Algorithmic Idea

### Upper-only phase

`UFairkSub` la mot threshold-greedy:

- duy tri nghiem `s`, tap nhan chua day `I`, va threshold `theta`.
- voi moi phan tu `e`, neu them vao support van giu matroid feasibility thi chon nhan `i_e in I` cho marginal gain lon nhat.
- neu gain vuot threshold thi chen `(e, i_e)`.
- khi chi con mot nhan chua day, paper quy phan con lai ve mot bai toan `submodular maximization under a matroid constraint` tren mot submodular slice `g(S) = f(sum_{e in S} <e, i>)`, roi goi mot SMM subroutine.

### Full fairness phase

`FairkSub` xay mot backbone lower-bound `u`, roi chia ngau nhien backbone nay thanh hai nua `u^(1), u^(2)`.

- moi nua xac dinh mot induced matroid `M_j`;
- chay `UFairkSub` tren moi induced instance de lay `x^(j)` giu upper bounds;
- sau do refines `x^(j)` bang cach chen tro lai mot phan cua backbone de nang lower-bound coverage;
- tra ve nghiem tot nhat trong `y^(1), y^(2), u`.

Random split la buoc giup lower-bound backbone duoc "tai su dung" ma khong pha matroid feasibility.

## Proof / Analysis Strategy

- Cho `UFairkSub`, paper xay transformed optimum `o_j` dong bo voi `s_j`, giong greedy proofs co dien nhung phai de y upper bounds tren tung nhan.
- Lemma 4 giu residual set `E_j = supp(o_j) \\ supp(s_j)` luon nam trong support optimum, nho do van matroid-independent.
- Lemma 5 cho per-step charging:
  - monotone: loss cua `o_j` bi chan boi `2 / (1 - epsilon)` lan gain cua `s_j`;
  - non-monotone: he so thanh `3 / (1 - epsilon)`.
- De xu ly lower bounds trong `FairkSub`, paper dung exchange property cua matroid bases de tach optimum thanh hai `k`-sets `o_1, o_2`, moi cai feasible cho mot induced subproblem sau random split. Ap dung `UFairkSub` len hai subproblems, roi dung random sampling lemma theo kieu Buchbinder cho phan backbone duoc chen lai.

## Key Techniques

- threshold greedy cho upper-fairness matroid
- giam label cuoi cung ve submodular matroid maximization
- transformed-optimum charging under fairness
- random split cua lower-bound backbone
- induced matroids quanh partial backbone
- fairness approximation thay vi exact fairness

## Key Lemmas Or Structural Claims

- Theorem 1: guarantees cua `UFairkSub`.
- Lemma 4: residual set sau moi transformation van nam trong support optimum.
- Lemma 5: per-iteration loss-vs-gain charging cho monotone / non-monotone.
- Theorem 2: guarantees cua `FairkSub`, bao gom relaxed fairness va approximation ratios.

## Delicate Points / Caveats

- Fairness guarantee khong exact: chi dat `floor(l_i / 2)` thay vi `l_i`.
- Authors khong co trong PDF; co ve la blind / review copy. Venue cung can verify.
- Ratios cuoi kha nho, dac biet non-monotone full fairness. Gia tri paper nam o viec mo duoc bai toan hon la ratio dep.
- Thuoc ve matroid constraint, khong chi total budget; do do khong nen so sanh truc tiep ratio voi Zhu et al. 2024.

## Extraction To Concepts

- Nen tao concept note `fair-k-submodular-maximization.md`.
- Reusable ingredient: reduced fairness guarantee qua random backbone split duoi matroid.

## Extraction To Syntheses

- `syntheses/k-submodular.md` nen bo sung fairness duoi matroid va phan biet exact fairness vs relaxed fairness.
- Open direction ro nhat la co dat exact lower bounds duoi matroid ma van giu constant factor cho non-monotone hay khong.

## Weaknesses / Limits

- Authors / venue chua ro.
- Approximation ratios cho full fairness kha yeu.
- Lower bounds bi mat mot nua trong guarantee, nen phai doc no nhu fairness-approximation chu khong phai full-feasibility exact.