acceptodds
Under review as a conference paper at ICLR 2027

Regret-aware Adaptive Scheduling for Resource-Constrained Auto-Bidding

Abstract

Frequent decision updates are crucial in dynamic environments, yet strict computational resource constraints severely restrict execution frequency. Existing methods for managing this trade-off either fail to align with horizon-wide system utility, rely on inflexible schedules, or incur profound search complexity through coupled action-timing exploration. To address these limitations, we propose AIGB-ReAL (Regret-Aware Adaptive ScheduLing), a novel framework for resource-constrained temporal scheduling. Conceptually, an unconstrained system can optimize actions across the horizon at every time step, whereas a limited compute budget requires merging adjacent steps to share the same action. We introduce Merge Regret to quantify the resulting reduction in optimal cumulative value after global re-optimization and estimate it using a Decision Landscape. For auto-bidding, this landscape is represented by volume-price response curves, guiding low-regret merging and responsive triggering with reduced reliance on joint exploration. Extensive experiments in simulated and real-world advertising systems demonstrate the superiority of our approach, achieving near-oracle performance with significantly fewer updates.

Primary area:
applications to robotics, autonomy, planning
Keywords:
Resource-Constrained Decision Making, Auto-Bidding, Reinforcement Learning

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_cdDtOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper introduces an algorithm for cost constrained auto-bidding that accounts for the fact that sometimes, for platform/scale reasons, the shading factor cannot be updated continuously over time. The algorithm output a criterion that, when satisfied, trigger an update. This criterion is based on a greedy algorithm that merge time intervals. Experiments on AuctionNet and online on live traffic are reported.

Critical strengths
  • The idea of merging greedily using marginal values offline to produce a criterion is interesting
  • I found the first half of the article well written
Critical weaknesses

I think the work would benefit from another round of polish.

  • see my questions: some passages are hard to parse because some quantities are not defined
  • the algorithm is only stated in the appendix. More focus should be put on the algorithm and the exact context, which in my opinion is too vague for now. In particular, section 4.2 is too vague.

For now, the contribution might be too narrow.

  • the solution is for a specific problem, does the methodology extends outside of the auto-bidding scope ? (btw does it connect with https://hal.science/hal-05456664v1/document ?)
  • strong modelling assumptions
  • could we get a more insightful theoretical result?
Questions for authors
  • please clarify what the optimal threshold τ\tau is.
  • page 5 , line 232, should ρJ′\rho_J' read ρA′\rho_A' instead?
  • line 265 page 5, what is UrU_r and where is it defined?
  • how do you justify the assumptions on the market dynamics?
  • what is the context that goes into the transformer?
  • can you clarify what BidDreamer is? Is it a contribution? An implementation of something that already existed?
1 comment
AuthorsOpenReview ↗

Clarifications on Theoretical Details, Algorithm, and Generalizability

We sincerely thank you for the constructive feedback. We are glad that our idea is appreciated. Below, we provide detailed responses to the questions and concerns.


1. Algorithm and Threshold (Q1, W1)

We provide a more detailed description of the algorithm and online execution in Section 4.2. For the definition of optimal threshold, please refer to response to Reviewer acvK.

2. Theorem 1 (Q2)

The subscript is JJ. Since the discrepancy in Eq. (8) is evaluated at xx, the proof applies the mean value theorem to ρJ\rho_J. From the common first-order conditions in Eq. (6), together with CI′(x)>0C_I'(x)>0 and CJ′(y)>0C_J'(y)>0, we obtain ρI(x)=GI′(x)CI′(x)=λ∗=GJ′(y)CJ′(y)=ρJ(y).\rho_I(x)=\frac{G_I'(x)}{C_I'(x)}=\lambda^*=\frac{G_J'(y)}{C_J'(y)}=\rho_J(y). Then, ∥ρI(x)−ρJ(x)∥=∥ρJ(y)−ρJ(x)∥.\|\rho_I(x)-\rho_J(x)\|=\|\rho_J(y)-\rho_J(x)\|. For x≠yx\ne y, the mean value theorem gives a point ξ∈(min⁡x,y,max⁡x,y)⊆D\xi\in(\min\\{x,y\\},\max\\{x,y\\})\subseteq D such that ρJ(y)−ρJ(x)=ρJ′(ξ)(y−x).\rho_J(y)-\rho_J(x)=\rho_J'(\xi)(y-x). Since ∣ρJ′(b)∣≥L>0|\rho_J'(b)|\ge L>0 throughout DD, we have ∣ρI(x)−ρJ(x)∣=∣ρJ′(ξ)∣∥y−x∣≥L∣y−x∣.\begin{aligned}|\rho_I(x)-\rho_J(x)|&=|\rho_J'(\xi)|\|y-x|\ge L|y-x|.\end{aligned} Therefore,∣x−y∣≤∣ρI(x)−ρJ(x)∣L.|x-y|\le\frac{|\rho_I(x)-\rho_J(x)|}{L}. Combining this with the spending-preserving candidate bound yields ΔL≤M‾2∣x−y∣2≤M‾2L2∣ρI(x)−ρJ(x)∣2,\Delta L\le\frac{\overline M}{2}|x-y|^2\le\frac{\overline M}{2L^2}|\rho_I(x)-\rho_J(x)|^2,where M‾=MI+MJ\overline M=M_I+M_J. If x=yx=y, the original optimum is already feasible after merging, so ΔL=0\Delta L=0 and the bound holds directly. A slope lower bound on ρI\rho_I instead would support the symmetric argument.

3. Definition of UrU_r (Q3)

UrU_r is introduced before Eq. (9). For the pair (Ir,Jr)(I_r,J_r) selected at merge step rr, UrU_r denotes the merge-loss upper bound: Ur=M‾r2Lr2(∣ρ^Ir(boff,r)−ρ^Jr(boff,r)∣+KL,rϵr+ηIr+ηJr)2.U_r=\frac{\overline M_r}{2L_r^2}\left(|\hat\rho_{I_r}(b_{off,r})-\hat\rho_{J_r}(b_{off,r})|+K_{L,r}\epsilon_r+\eta_{I_r}+\eta_{J_r}\right)^2.

4. Market Dynamics Assumptions (Q4, W2.2)

Our merge-loss analysis requires only general regularity conditions on the response curves, without assuming a specific parametric form or temporal stationarity, allowing θt\theta_t to vary over time. Increasing cost and decreasing marginal efficiency are economically motivated, while the curvature and slope bounds are local regularity assumptions used to derive the merge-loss theoretically. The exponential parameterization satisfies these properties, and Appendix D provides empirical support. Besides, Appendix F verifies these properties for an alternative Hill parameterization, and Table 5 demonstrates competitive performance.

5. Transformer Context (Q5)

  • Time and budget: Normalized remaining time and budget.
  • Historical statistics: Mean bids, winning costs, pValue, conversion rates, and win rates over all previous and the last three ticks.
  • Traffic statistics: Current mean pValue and PV count, plus PV counts over the last three and all previous ticks.

6. BidDreamer (Q6)

BidDreamer serves as the bidding policy in our online experiments. It is not a separate contribution, and our contribution focuses on the scheduling mechanism.

7. Generalizability (W2.1)

The underlying methodology addresses a more general resource-constrained sequential decision problem. Consider a horizon of TT decision steps, where each step tt is associated with a reward function Rt(u)R_t(u) and a resource consumption function Ct(u)C_t(u), uu denoting a continuous action. Given a total resource budget BB and a maximum number of KK action updates, the problem can be formulated as: max⁡P,uII∈P∑I∈P∑t∈IRt(uI)s.t.∑I∈P∑t∈ICt(uI)≤B,&∣P∣≤K,\begin{aligned}\max_{P,\\{u_I\\}{I\in P}}\quad&\sum_{I\in P}\sum_{t\in I}R_t(u_I) \quad\text{s.t.}&\sum_{I\in P}\sum_{t\in I}C_t(u_I)\le B,\&|P|\le K,\end{aligned} where PP is a partition of the time horizon, and all steps within each interval II share the same action uIu_I. This formulation is independent of auction-specific mechanisms and can be extended to other scenarios, such as LLM inference resource scheduling, energy management, and dynamic pricing.

Besides, CUVET and our work address different problems. CUVET focuses on treatment assignment by partitioning the user feature space to optimize personalized treatment allocation, whereas our work addresses resource-constrained decision scheduling, aiming to determine when actions should be updated under a limited computational budget.

8. Insight (W2.3)

Identifying and preserving critical decision opportunities is essential for effective decision scheduling. Our analysis suggests that decision updates should be driven by meaningful changes in the Decision Landscape. When the underlying reward-cost trade-offs remain similar, additional updates may be unnecessary. Theoretically, we establish that the performance loss induced by sharing an action across adjacent intervals is upper-bounded by a quadratic function of their marginal-efficiency discrepancy, providing a principled criterion for adaptively identifying which decision boundaries can be safely removed and which should be preserved. Our experimental results further support this theoretical insight.

Reviewer_acvKOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies when an auto-bidding agent should update its bidding multiplier under a limited decision budget. It introduces Merge Regret, defined as the reduction in globally optimized value when adjacent intervals share a decision, and derives a bound using marginal-efficiency curves. AIGB-ReAL combines learned response curves, offline greedy partitioning, and online threshold-based triggering. Evaluation includes AuctionNet simulations and a large-scale advertising A/B test.

Critical strengths
  1. The scheduling objective is well motivated. Defining update value through the loss after global budget re-optimization captures an important limitation of triggers based only on local state changes. The pairwise merge-loss bound provides a useful connection between economic response curves and the cost of reducing decision frequency.

  2. The evaluation includes meaningful practical evidence. The paper compares several scheduling paradigms, examines different temporal granularities, and ablates the latent representation and curve-based signal. The deployment involving approximately 600,000 advertisers provides evidence that the broader approach can operate in a realistic advertising system.

Critical weaknesses
  1. The connection between the offline analysis and online algorithm is incomplete. Section 3.4 bounds the accumulated loss along a particular merging sequence, but does not establish that greedy merging produces an optimal partition or that the online threshold policy inherits this bound. Section 4.2 also leaves the functional divergence and threshold-extraction procedure insufficiently specified. Furthermore, the described threshold rule does not explain how the hard update budget in Eq. (1) is enforced online.

  2. The online experiment does not isolate the claimed resource-efficiency advantage. The comparison changes the decision granularity from 15 minutes to 1 minute without reporting matched update counts, QPS, or total computation. The cost of repeatedly evaluating the encoder and trigger is also unclear. Consequently, the observed business improvements do not establish that regret-aware scheduling achieves better performance under the same computational constraint.

  3. The offline evidence is too narrow to support the broad superiority claims. Section 5 evaluates one target advertiser with a fixed decision budget of K=10K=10. Performance differences against competitive baselines are sometimes small: at T=144T=144, the scores are 25.62 versus 25.50 for WaitWatch, while at T=96T=96, SAR outperforms AIGB-ReAL. The reported marginal standard errors do not establish the significance of paired differences. Broader advertiser and budget coverage is needed to determine how consistently the method helps.

Questions for authors
  1. What are the exact definitions of the online divergence and threshold-extraction procedure, and how is the remaining update budget enforced during online execution?

  2. Can you provide a comparison with the same bidding policy and matched total computational resources, including trigger evaluation costs? What were the actual update counts and QPS in the online experiment?

  3. Do the scheduling gains persist across multiple target advertisers and decision budgets, with paired uncertainty estimates?

1 comment
AuthorsOpenReview ↗

Clarifications on Online Execution, Computational Costs, and Expanded Evaluation

We sincerely thank you for the constructive feedback. We are glad that our motivation and practical evaluation are appreciated. Below, we clarify the online execution, computation, and additional experiments.


1. Online Execution and Update Budget (W1, Q1)

Let aa be the last update time, B=[bmin⁡,bmax⁡]\mathcal B=[b_{\min},b_{\max}] the bidding interval, and G\mathcal G the comparison grid. We compute $ d_t= \max_{b\in\mathcal G} |\hat\rho_t(b)-\hat\rho_a(b)|, \hat\rho_t(b)=\frac{\hat G_t'(b)}{\hat C_t'(b)}. $ Starting from TT intervals, the offline procedure performs T−KT-K merges until KK intervals remain. Let dmerge(r)d_{\mathrm{merge}}^{(r)} denote the distance recorded for the pair selected at merge rr. The threshold is $ \tau=d_{\mathrm{merge}}^{(T-K)}. $ More details about the online update are described in our response to Reviewer mRzw (W1&W2&W3).

2. Computation Efficiency (W2, Q2)

The one-minute online setting T=1440T=1440 uses an update target of K=96K=96, corresponding to the nominal daily update count of the 15-minute baseline. The update count is provided in our response to Reviewer mRzw (W2).

At our platform’s scale, the original fixed 15-minute control schedule enables full advertiser coverage within the QPS limit. Directly increasing policy calls to once per minute would exceed this limit, as policy execution and bid-parameter distribution incur substantial operational costs. We therefore introduce a lightweight trigger that assesses update opportunities every minute and selectively invokes the bidding policy. Trigger evaluation is an essential component of our design for assessing update opportunities every minute while respecting the QPS constraint. It determines whether an expensive policy invocation is warranted. Although this introduces additional computation, the lightweight trigger consumes substantially fewer resources than policy execution and bid-parameter distribution.

With comparable daily update counts, our main contribution is to identify more effective update times from finer-grained decision opportunities. Deployment results also show that the share of control updates allocated to low-spend campaigns decreased by 16 percentage points, with a corresponding increase for medium- and high-spend campaigns. Separately, capacity planning projects a serving-capacity increase exceeding 33%.

3. Broader Evaluation and Paired Uncertainty Estimates (W3, Q3)

Advertiser coverage. K=10 with 9 additional advertisers at T=48T=48, selected by different budget tiers: low (#5, #29, #42), middle (#19, #26, #35), and high (#23, #14, #44).

MethodScoreCostConvPaired ΔScore ± SEHolm-adjusted pp
Ours24.96±0.962192.18±68.4528.42±1.01——
Random23.85±0.952042.19±68.4226.85±1.01+1.11±0.310.006
Uniform (TTC)23.92±0.972007.24±68.2026.71±1.02+1.04±0.300.008
WaitWatch (ETC)22.08±1.041611.97±63.6223.53±1.05+2.88±0.50<0.001
Interval-RL (DAR)23.82±0.942066.49±68.7126.88±1.00+1.14±0.250.001
Safe Action Rep (SAR)24.09±0.912217.26±69.4227.84±0.99+0.87±0.290.020
JointExploration (LICRA)8.06±0.323236.07±54.0221.44±0.44+16.90±0.77<0.001

ΔScore denotes AIGB-ReAL minus the corresponding baseline. Paired inference uses 32 episode-level clusters, averaging differences across the 10 advertisers within each episode seed. P-values are Holm-adjusted across baseline comparisons within this setting.

Adaptation coverage. Update budget varying K∈5,15,20,25K\in\\{5,15,20,25\\} at T=48T=48.

KK5152025
MethodScoreppCostConvScoreppCostConvScoreppCostConvScoreppCostConv
Ours23.12±2.40—1914.46±175.2523.88±2.3027.81±1.94—2325.73±138.4028.62±1.8629.68±1.78—2464.44±125.0430.16±1.7129.56±1.76—2501.44±113.6030.12±1.67
Random21.01±2.590.0431653.47±182.9121.66±2.5324.80±2.310.0052032.22±162.8525.43±2.2226.96±2.010.0572217.71±144.2127.51±1.9127.35±1.840.0832343.63±131.1628.07±1.77
Uniform(TTC)20.44±2.660.0431584.35±190.4321.02±2.6124.65±2.200.0052104.06±156.6725.51±2.1026.69±1.900.0152278.53±137.2827.36±1.8328.84±1.820.4342448.95±122.6229.50±1.72
WaitWatch(ETC)18.42±2.42<0.0011372.56±164.7318.94±2.3719.64±2.50<0.0011485.65±167.4120.28±2.4419.64±2.50<0.0011485.65±167.4120.28±2.4419.64±2.50<0.0011485.65±167.4120.28±2.44
Interval-RL(DAR)20.43±2.650.0401620.32±190.1721.03±2.5926.13±2.010.1772210.57±149.2426.78±1.9128.67±1.800.2762381.81±132.1028.97±1.7527.86±1.760.4342402.42±131.2528.41±1.70
Safe Action Rep(SAR)20.92±2.590.0431658.64±190.5421.53±2.5225.56±1.950.1772220.71±157.1426.44±1.8926.32±2.010.0202267.34±152.4227.03±1.9425.76±2.090.0132255.40±153.7926.56±2.02
JointExploration (LICRA)9.50±1.31<0.0012899.95±0.0118.78±0.899.50±1.31<0.0012899.95±0.0118.78±0.899.50±1.31<0.0012899.95±0.0118.78±0.899.50±1.31<0.0012899.95±0.0118.78±0.89
Reviewer_mRzwOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates the problem of scheduling bidding policy updates under limited computational resources. In real-time bidding (RTB) systems, computational constraints, such as Queries Per Second (QPS) limits, prevent bidding policies from being updated at every time step. To address this challenge, the authors propose AIGB-ReAL (Regret-Aware Adaptive Scheduling), a framework designed to optimize the timing of policy updates under a limited update budget.

Critical strengths
  1. The paper addresses a practically relevant problem. The problem is well motivated by real-world computational constraints and provides a valuable perspective on sequential decision-making under limited resources.

  2. The proposed method is reasonably designed and supported by theoretical analysis. AIGB-ReAL decouples update scheduling from bidding policy optimization, allowing different bidding policies to be employed without retraining the entire scheduling mechanism. This modular design offers practical flexibility. Furthermore, the theoretical analysis provides support for the proposed response-curve-based scheduling approach.

  3. The experiments include comparisons with multiple baselines and evidence from real-world deployment. The evaluation covers several representative baseline methods and includes online A/B testing, providing empirical evidence of the practical applicability of the proposed framework.

Critical weaknesses
  1. There is a gap between the theoretical guarantees and the actual online algorithm. The theoretical upper bound on Merge Regret is not explicitly shown to apply to the distance-based threshold triggering mechanism used during online execution. This weakens the paper's central theoretical contribution.

  2. The online triggering algorithm does not explicitly guarantee compliance with the strict update budget constraint. The central problem considered in this paper is to maximize performance under a budget of at most K policy updates. Although the offline greedy merging procedure produces a partition containing exactly K intervals, the online algorithm relies on a fixed-threshold triggering mechanism, which does not inherently guarantee that the actual number of updates remains within K. For example, when the market undergoes frequent and substantial changes, the online distance metric may repeatedly exceed the threshold, potentially causing the number of updates to exceed the prescribed budget. Conversely, during relatively stable market conditions, the number of triggered updates may be substantially smaller than K. The authors should clarify how the proposed online algorithm enforces the update budget constraint under dynamically changing market conditions.

  3. The optimality claims regarding the greedy algorithm are not sufficiently supported. The loss bounds established in Theorem 1 and Equation (9) do not guarantee that the greedy algorithm produces an optimal K-interval partition, nor do they establish an approximation ratio relative to the globally optimal partition.

Questions for authors

Please refer to Weaknesses.

1 comment
AuthorsOpenReview ↗

Clarifications on Theoretical Guarantees, Update Budgets, and Greedy Scheduling

We sincerely thank you for the constructive feedback. We are glad that the motivation, method, and empirical results are appreciated. Below, we clarify the theoretical guarantees, update budget, and greedy optimality. We have uploaded a revised manuscript.


1. Theory–algorithm gap (W1)

The offline stage can construct partitions using complete historical trajectories. Online execution, however, must make causal decisions without future observations. We therefore use the curve-distance comparison as a practical online surrogate.

To make the connection explicit, let aa be the last update time and I=[a,t−1]I=[a,t-1] the holding interval. The distance satisfies $ \sup_{b\in\mathcal B} |\hat\rho_s(b)-\hat\rho_a(b)|\le d_s. $ For a threshold-based holding decision, ds≤τd_s\le\tau throughout I∪{t}I\cup\{t\}, with da=0d_a=0. Let η\eta denote the maximum absolute error of the marginal-efficiency estimates over these timesteps and the triangle inequality gives ∣ρs(b)−ρt(b)∣≤∣ρs(b)−ρ^s(b)∣+∣ρ^s(b)−ρ^a(b)∣+∣ρ^a(b)−ρ^t(b)∣+∣ρ^t(b)−ρt(b)∣≤η+ds+dt+η≤2τ+2η.\begin{aligned}|\rho_s(b)-\rho_t(b)|&\le |\rho_s(b)-\hat\rho_s(b)|+|\hat\rho_s(b)-\hat\rho_a(b)|+|\hat\rho_a(b)-\hat\rho_t(b)|+|\hat\rho_t(b)-\rho_t(b)| \le \eta+d_s+d_t+\eta\le 2\tau+2\eta.\end{aligned}

Since interval efficiency is a weighted average, ρI(b)=∑s∈Iws(b)ρs(b),ws(b)=Cs′(b)∑u∈ICu′(b),\rho_I(b)=\sum_{s\in I}w_s(b)\rho_s(b),w_s(b)=\frac{C_s'(b)}{\sum_{u\in I}C_u'(b)}, we obtain ∣ρI(b)−ρt(b)∣≤∑s∈Iws(b)∣ρs(b)−ρt(b)∣≤2τ+2η.|\rho_I(b)-\rho_t(b)|\le\sum_{s\in I}w_s(b)|\rho_s(b)-\rho_t(b)|\le 2\tau+2\eta. Then $\Delta L_t \le \frac{\overline M_t}{2L_t^2}|\rho_I(x_t)-\rho_t(x_t)|^2\le \frac{\overline M_t}{2L_t^2}(2\tau+2\eta)^2. $

Curve Estimation. We use GMV and cost prediction accuracy as an empirical proxy for the quality of the estimated marginal-efficiency representation. We report R2R^2 after applying the log1p transformation to predictions and observations, providing empirical support for the learned response representation.

TT4896144288
GMV R2R^20.8920.8180.8560.876
Cost R2R^20.9060.8640.8760.879

Trigger Agreement. We compare threshold-based triggers with those obtained ex post through greedy optimization. Let PiP_i and GiG_i denote the respective trigger sets for trajectory ii. We report precision and recall averaged across trajectories: $ Precision=\frac{1}{N}\sum_{i=1}^{N} \frac{|P_i\cap G_i|}{|P_i|}, Recall=\frac{1}{N}\sum_{i=1}^{N} \frac{|P_i\cap G_i|}{|G_i|}. $

MetricPrecisionRecall
TT48961442884896144288
Random0.4030.3230.2940.2510.3930.3040.2700.228
Ours0.8000.8360.7990.7780.7830.7940.7610.736

For the online experiment with 1440 timesteps and 96 control updates, the results are summarized below.

GMV R2R^2Cost R2R^2PrecisionRecall
0.8530.6770.8920.652

These results support the accuracy of the learned response curves and show agreement between threshold-based triggers and greedy optimization triggers.

2. Online Update Budget (W2)

In our current implementation, KK determines the offline update budget. Starting from TT intervals, we merge until KK intervals remain and set τ=dmerge(T−K),\tau=d_{\mathrm{merge}}^{(T-K)}, and online execution uses the mean threshold. Here, KK represents a target average update frequency rather than a hard per-advertiser cap. Individual advertisers may receive more or fewer updates, while the objective is to keep the average policy-call count close to the target.

We report the corresponding online results with T=1440T=1440 and target K=96K=96. Each trigger invokes the bidding policy, which produces a bid-adjustment parameter. Besides, if this parameter is below the action threshold, the existing bidding multiplier is also retained. The observed mean counts remain close to the target of 96.

Metric (per advertiser)MeanMedian
Trigger events105.884
Effective changes91.474

3. Greedy Method (W3)

We agree that Theorem 1 and Eq. (9) do not establish global optimality of the greedy partition. However, they provide a conditional additive bound on the optimality gap.

Let $ J_K^*=\max_{|\mathcal P|\le K}J(\mathcal P).$

Since JK∗≤J(Pdense)J_K^*\le J(\mathcal P_{\mathrm{dense}}), Eq. (9) implies

$0\le J_K^*-J(\mathcal P_g) \le J(\mathcal P_{\mathrm{dense}})-J(\mathcal P_g) \le\sum_r U_r, $ provided the per-merge bounds hold.

Greedy merging is a common heuristic for combinatorial optimization. To empirically assess the quality of greedy merging, we evaluate the empirical approximation ratio of greedy merging relative to the Dynamic Programming (DP) optimum under the distance surrogate objective: $ E_{sq}(P)=\sum_{S \in P} \sum_{t \in S} d_{\rho}(\mu_S, x_t)^2, $where μS\mu_S is the mean representation of interval SS.

$ \text{Approximation Ratio} =\frac{E_{sq}(P_{DP})}{E_{sq}(P_g)}. $

TT4896144288
AR0.9150.9090.8540.798

DP requires O(KT2)O(KT^2) time and returns a specific partition without directly providing a triggering threshold. We adopt greedy merging as a practical alternative and will clarify the scope of its guarantee.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.