Pith. sign in

REVIEW 2 major objections 4 minor 115 references

How much data is sufficient to learn high-performing algorithms? Generalization guarantees for data-driven algorithm design

T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves a unified sample-complexity theorem for data-driven algorithm design whenever an algorithm's performance is piecewise-structured in its parameters.

desk verdict Genuinely unifying sample-complexity theorem, but the application lemmas have an unhandled tie-breaking problem at parameter boundaries that, as written, breaks the piecewise-decomposability claims. read the letter →

arxiv 1908.02894 v4 pith:MQBWKREK submitted 2019-08-08 cs.LG stat.ML

Maria-Florina Balcan , Dan DeBlasio , Travis Dick , Carl Kingsford , Tuomas Sandholm , Ellen Vitercik This is my paper · ORCID
classification cs.LGstat.ML
keywords data-drivenalgorithmdesignsamplecomplexitygeneralizationboundspseudo-dimensiondualclasspiecewisedecomposabilityconfigurationsequencealignment
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tries to establish a general theorem saying how many training instances suffice to guarantee that a parameter setting with strong average performance will also perform well on unseen instances. Its central claim is that whenever every fixed instance induces a performance function over the parameter space that is piecewise constant, piecewise linear, or more generally piecewise structured, the pseudo-dimension of the utility class is controlled by the complexity of the boundary and piece classes. Concretely, the pseudo-dimension is O((Pdim(F*) + VCdim(G*)) ln(Pdim(F*) + VCdim(G*)) + VCdim(G*) ln k), which translates into a uniform bound of O~(H sqrt((Pdim(U) + ln(1/delta))/N)) on the gap between training and expected performance. A sympathetic reader would care because this is a single structural condition that unifies previous case-by-case guarantees for greedy algorithms, clustering, integer programming, and selling mechanisms, and it gives new guarantees for voting mechanisms and computational biology algorithms.

What carries the argument

The carrying object is the dual class U* = {u_x | x in X}, the set of performance functions that fix a problem instance and vary the parameter vector; each u_x maps the primal class U to [0,H]. The paper combines two complexity measures: the pseudo-dimension of the dual piece class F* and the VC-dimension of the dual boundary class G*. Its proof counts sign patterns: for N instances, the union of their boundary functions induces at most (ekN)^{VCdim(G*)} regions of the parameter space, by Lemma 3.4 and Sauer's lemma on the dual boundary class; within any one region, the N piece functions can produce at most (eN)^{Pdim(F*)} labelings relative to fixed thresholds. Multiplying the region count by the per-region labeling count and solving 2^N <= (ekN)^{VCdim(G*)} (eN)^{Pdim(F*)} yields the pseudo-dimension bound.

What would settle it

Run the proof's core counting inequality directly: build N dual functions from a candidate (F,G,k)-piecewise decomposable class, enumerate all sign patterns relative to thresholds, and check whether 2^N exceeds (ekN)^{VCdim(G*)} (eN)^{Pdim(F*)}; exceeding it would contradict the proof of Theorem 3.3 and give a concrete counterexample.

Watch

Extended reading notes

Core claim

The central discovery is that the hard part of data-driven algorithm design is not the particular algorithm but the geometry of how its performance depends on its parameters. For a fixed problem instance, the algorithm's utility as a function of the parameter vector belongs to the dual class U*; this paper defines U* to be (F,G,k)-piecewise decomposable when at most k boundary functions from G partition the parameter space into regions and on each region the utility equals one of the piece functions from F. Theorem 3.3 states that under this condition Pdim(U) = O((Pdim(F*) + VCdim(G*)) ln(Pdim(F*) + VCdim(G*)) + VCdim(G*) ln k). Feeding this through the classic Pollard pseudo-dimension bound, the paper obtains that with probability 1-delta over N training instances, for every parameter setting the difference between average and expected performance is O~(H sqrt((Pdim(U) + ln(1/delta))/N)). This establishes that piecewise structure alone, regardless of how parameters are tuned, is enough for uniform convergence.

Load-bearing premise

The load-bearing premise is the paper's co-optimal-constant assumption: in any region of parameter space where the set of co-optimal solutions is fixed, the algorithm's output is also fixed, so the utility function cannot vary because of tie-breaking within that region.

Editorial extensions

If this is right

  • For any algorithm family whose dual functions are (F,G,k)-piecewise decomposable, O~(H^2 (Pdim(F*) + VCdim(G*) ln k)/epsilon^2) training instances guarantee that empirical average performance is within epsilon of expected performance uniformly over all parameter settings.
  • The theorem recovers the existing generalization bounds for greedy knapsack and maximum-weight independent set algorithms, linkage-based clustering, branch-and-bound and SDP rounding for integer programs, and revenue-maximizing selling mechanisms.
  • New guarantees follow for computational biology: pairwise and progressive sequence alignment and RNA folding have pseudo-dimension O(ln n) in the affine-gap model, while TAD prediction has pseudo-dimension O(n^2), all under piecewise-constant duals.
  • Neutral affine maximizer voting mechanisms have pseudo-dimension O(n ln m), and a matching lower bound of Omega(n) shows the main theorem is tight up to logarithmic factors.
  • Because the guarantees do not depend on how the parameter search is conducted, they apply equally to manual tuning, automated configuration, and any future search procedure.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same counting argument could in principle yield sample-complexity bounds for portfolio-based algorithm selection, where the learned object is a mapping from instance features to an algorithm choice rather than a single parameter vector; the paper lists portfolio learning as future work.
  • The theorem's dependence on VCdim(G*) rather than the primal boundary complexity suggests a transferable design principle: high-dimensional parameter spaces are tractable whenever the boundary class is simple, as in Lemma 3.10 where halfspace boundaries give O(d ln(dk)).
  • A testable extension would be to relax the co-optimal tie-breaking assumption: algorithms whose output is not fixed on open co-optimal regions may still admit a decomposable dual if the tie-breaking rule itself is piecewise structured, extending the computational biology bounds.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper develops a unified generalization framework for data-driven algorithm design. It introduces the notion of an (F,G,k)-piecewise-decomposable dual function class and proves Theorem 3.3, which bounds the pseudo-dimension of the primal parameterized algorithm class in terms of the pseudo-dimension of F* and the VC-dimension of G*. This yields sample-complexity guarantees that apply to any parameter tuning procedure. The authors instantiate the framework for sequence alignment, RNA folding, topologically associating domain prediction, and neutral affine maximizers, and they show that prior bounds for clustering, integer programming, greedy algorithms, and revenue-maximizing mechanisms are recovered as special cases. They also provide lower bounds showing tightness up to logarithmic factors for sequence alignment and voting mechanisms, and they complement the theory with experiments on alignment accuracy and mechanism-design estimation error.

Significance. If the framework is fully correct, it is a significant unification: it replaces case-by-case pseudo-dimension analyses with a single structural condition, and it yields new bounds for computational biology algorithms and voting mechanisms. The proof of Theorem 3.3 is transparent and rests on standard Sauer/Pollard arguments, and the paper carefully extracts the key counting lemma (Lemma 3.4). The recovery of prior results is a genuine strength, as is the inclusion of tightness lower bounds for two concrete application families. The experimental section is a useful illustration, though it is not the main contribution. The main caveat, developed below, is that the application lemmas prove piecewise constancy only on open cells of hyperplane arrangements, whereas the definition of piecewise decomposability requires equality on all parameter vectors, including lower-dimensional tie points.

major comments (2)
  1. [Section 4, Definition 3.2, and Lemmas 4.1, 4.2, 4.4, 4.5, 4.6, 5.1] The proof of Theorem 3.3 and the application lemmas require the equality u*_x(u_rho) = f_{b_x(rho)}(u_rho) to hold for every parameter vector rho, including parameter values lying on the boundary hyperplanes. The lemmas only establish that the algorithm's output is fixed on the open connected components of R^d \ H. On a boundary face, the strict sign vector b is the same as on one adjacent open cell, and the construction either assigns the piece function of that adjacent cell or assigns f_0 to sign patterns not corresponding to open cells. If tie-breaking at the boundary selects a different co-optimal solution---or a solution that is co-optimal only on the face---the utility at the boundary differs from the assigned piece function, so the decomposability equality fails. The co-optimal-constant assumption does not repair this, because the set of co-optimal solutions on the face is different from the set on either adjacent open cell, and the assumption only fixes the output once that set is fixed. Since pseudo-dimension is a worst-case quantity over all parameters, these lower-dimensional tie points cannot be ignored. This affects the pseudo-dimension bounds claimed for sequence alignment, RNA folding, TAD prediction, and voting mechanisms. A repair would be to include both strict and non-strict halfspace indicators as boundary functions so that each face of the arrangement receives its own sign pattern, and to assign a piece function to every such face; with the co-optimal-constant property on faces, the asymptotic bounds should be preserved up to constant factors.
  2. [Abstract and Section 3, Theorem 3.6] The abstract states that the guarantees are 'tight up to logarithmic factors in the worst case,' but the lower bounds in Theorem 3.6 are proved only for two concrete classes (sequence alignment and voting mechanisms), not for the general (F,G,k)-piecewise-decomposable setting. Please qualify the tightness claim so that it refers to the demonstrated lower-bound instances, or provide a general lower bound matching Theorem 3.3.
minor comments (4)
  1. [Section 7.2.1, Figure 7] The caption and the body text appear to disagree about which line is the anonymous-SPA upper bound and which is the non-anonymous-SPA empirical estimation error: the caption says the orange dashed line is the AA upper bound and the blue solid line is the AN lower bound, while the text near Equation (22) describes the blue solid line as the right-hand side of Equation (22). Please reconcile these labels.
  2. [Page 9, proof of Theorem 3.3] The word 'pseduo-dimension' is misspelled and should be 'pseudo-dimension'.
  3. [References] Reference [16] is malformed: it appears to merge the authors of the present paper with unrelated text ('Dimitris Bertsimas and Vassilis Digalakis Jr.'). Please correct this entry.
  4. [Section 4] The term 'co-optimal-constant' is used informally in the text and in Theorem 4.3; please provide a formal definition at its first use, since it is central to the tie-breaking discussion.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main pseudo-dimension theorem and the novel computational-biology and voting-mechanism bounds are derived from independent structural decompositions; the recovery of prior bounds is a consistency check, not a load-bearing input.

full rationale

The paper's central derivation is self-contained. Theorem 3.3 bounds Pdim(U) in terms of Pdim(F*) and VCdim(G*) via a double-counting argument over sign patterns, relying on Sauer's lemma applied to dual classes; this is a standard, independent chain of reasoning with no fitted parameters or self-defined benchmarks. The novel application lemmas (4.1, 4.2, 4.4, 4.5, 4.6, 5.1) explicitly construct piecewise decompositions for sequence alignment, RNA folding, TAD prediction, and neutral affine maximizers, either from first principles or using classical external results (e.g., parametric alignment bounds [36, 50, 81] and Rolle's theorem via [96]). These constructions do not assume the pseudo-dimension conclusion they are used to derive. The paper's Section 6 recovers prior generalization bounds by citing structural lemmas from earlier work, some of which is by the same authors; however, this recovery is presented expressly as a consistency check and is not used to prove the main theorem or the novel bounds. The prior structural lemmas are independent inputs, and their use does not reduce a claimed prediction to a fitted parameter or to a self-citation chain. The lower bounds in Theorems 4.3 and 5.2 are built from explicit shattering constructions rather than from the upper-bound machinery. Overall, the derivation chain does not exhibit any step where the conclusion is equivalent by definition or by construction to the assumptions.

Assumptions & free parameters 0 free parameters · 8 assumptions · 0 invented entities

No free parameters are fitted; all bounds are universal constants and problem-size parameters. The axioms are standard learning-theory counting tools plus the explicit structural and tie-breaking assumptions the applications need. No invented entities are introduced.

assumptions (8)
  • standard math Pollard pseudo-dimension uniform convergence theorem (Eq. 2).
    Converts any Pdim(U) bound into a generalization guarantee; classical result used throughout the paper.
  • standard math Sauer's lemma for VC classes, applied to dual boundary classes.
    Core counting step in Lemma 3.4; standard combinatorics.
  • standard math Pseudo-dimension dichotomy counting: any N functions in F induce at most (eN)^Pdim(F*) sign patterns.
    Used in Theorem 3.3 after partitioning the parameter space.
  • standard math VCdim of halfspace indicators and Pdim of linear functions in R^d are O(d).
    Used in Lemma 3.10 for piecewise-linear duals.
  • standard math Rolle's theorem and Tossavainen's bound on roots of exponential sums.
    Bounds the number of TAD dual pieces in Lemma 4.6.
  • domain assumption Co-optimal-constant tie-breaking: algorithm output is fixed wherever the set of co-optimal solutions is fixed.
    Stated in Section 4; needed for utility to be piecewise constant in sequence alignment, RNA folding, and TAD applications.
  • domain assumption Prior parametric alignment bounds: O(n^(3/2)) distinct alignments for the affine-gap model and HMM alignment bounds.
    Imported from references [36, 50, 81] to obtain improved decomposability in Lemmas 4.2 and C.6.
  • domain assumption Utility functions take values in [0,H] and instances are drawn i.i.d. from an unknown distribution D.
    This is the standard distributional learning model for data-driven algorithm design, adopted from Gupta and Roughgarden.

how reviews work

0 comments
Cite this review

Pith. "Pith review of How much data is sufficient to learn high-performing algorithms? Generalization guarantees for data-driven algorithm design." pith.science (2026). https://pith.science/paper/MQBWKREK

@misc{pith2026190802894,
  author       = {Pith},
  title        = {Pith review of: How much data is sufficient to learn high-performing algorithms? Generalization guarantees for data-driven algorithm design},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MQBWKREK}},
  note         = {Machine review of arXiv:1908.02894}
}
read the original abstract

Algorithms often have tunable parameters that impact performance metrics such as runtime and solution quality. For many algorithms used in practice, no parameter settings admit meaningful worst-case bounds, so the parameters are made available for the user to tune. Alternatively, parameters may be tuned implicitly within the proof of a worst-case approximation ratio or runtime bound. Worst-case instances, however, may be rare or nonexistent in practice. A growing body of research has demonstrated that data-driven algorithm design can lead to significant improvements in performance. This approach uses a training set of problem instances sampled from an unknown, application-specific distribution and returns a parameter setting with strong average performance on the training set. We provide a broadly applicable theory for deriving generalization guarantees that bound the difference between the algorithm's average performance over the training set and its expected performance. Our results apply no matter how the parameters are tuned, be it via an automated or manual approach. The challenge is that for many types of algorithms, performance is a volatile function of the parameters: slightly perturbing the parameters can cause large changes in behavior. Prior research has proved generalization bounds by employing case-by-case analyses of greedy algorithms, clustering algorithms, integer programming algorithms, and selling mechanisms. We uncover a unifying structure which we use to prove extremely general guarantees, yet we recover the bounds from prior research. Our guarantees apply whenever an algorithm's performance is a piecewise-constant, -linear, or -- more generally -- piecewise-structured function of its parameters. Our theory also implies novel bounds for voting mechanisms and dynamic programming algorithms from computational biology.

Figures

Figures reproduced from arXiv: 1908.02894 by the authors.

Figure 1
Figure 1. A piecewise-constant function over R 2 ≥0 with linear boundary functions g (1) and g (2) . function value on each subset from this partition. More formally, the dual class U ∗ is (F, G, k)-piecewise decomposable if for every problem in￾stance, there are at most k boundary functions from a set G (for example, the set of linear sepa￾rators) that partition the parameter space into regions such that within each region, … view at source ↗
Figure 2
Figure 2. Boundary functions partitioning R 2 . The arrows indicate on which side of each function g (i) (ρ) = 0 and on which side g (i) (ρ) = 1. For example, g (1) (ρ1) = 1, g (1) (ρ2) = 1, and g (1) (ρ3) = 0. Definition 3.1 (Dual class [3]). For any domain Y and set of functions H ⊆ R Y, the dual class of H is defined as H∗ =  h ∗ y : H → R | y ∈ Y [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Each solid line is a function with bounded oscillations and each dotted line is an arbitrary [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figures from the paper (7 more)
Figure 4
Figure 4. Figure 4: The form of u(0,ρ[2],0)  S (1) 1 , S(1) 2  as a function of the indel parameter ρ[2]. When ρ[2] ≤ 1 6 , the algorithm returns the bottom alignment. When 1 6 < ρ[2] ≤ 1 4 , the algorithm returns the alignment that is second to the bottom. When 1 4 < ρ[2] ≤ 1 2 , the a…
Figure 5
Figure 5. Figure 5: Parameter space decomposition for a single example. [PITH_FULL_IMAGE:figures/full_fig_p035_5.png]
Figure 6
Figure 6. Figure 6: Pairwise sequence alignment experiments showing the average accuracy on training and [PITH_FULL_IMAGE:figures/full_fig_p036_6.png]
Figure 7
Figure 7. Figure 7: Revenue maximization experiments. We vary the size of the training set, [PITH_FULL_IMAGE:figures/full_fig_p038_7.png]
Figure 8
Figure 8. Figure 8: Neutral affine maximizer experiments. We vary the size of the training set, [PITH_FULL_IMAGE:figures/full_fig_p041_8.png]
Figure 9
Figure 9. Figure 9: Illustration of Claim C.3: we can assume that each [PITH_FULL_IMAGE:figures/full_fig_p054_9.png]
Figure 10
Figure 10. Figure 10: This figure illustrates an example of the progressive sequence alignment algorithm in [PITH_FULL_IMAGE:figures/full_fig_p059_10.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

115 extracted references · 73 canonical work pages

  1. [1]

    SCIP: solving constraint integer programs

    Tobias Achterberg. SCIP: solving constraint integer programs. Mathematical Programming Computation, 1(1):1–41, 2009

    2009

  2. [2]

    Learning to prune: Speeding up repeated computations

    Daniel Alabi, Adam Tauman Kalai, Katrina Ligett, Cameron Musco, Christos Tzamos, and Ellen Vitercik. Learning to prune: Speeding up repeated computations. In Conference on Learning Theory (COLT), 2019

    2019

  3. [3]

    Densit´ e et dimension

    Patrick Assouad. Densit´ e et dimension. Annales de l’Institut Fourier , 33(3):233–282, 1983

    1983

  4. [4]

    Data-driven algorithm design

    Maria-Florina Balcan. Data-driven algorithm design. In Tim Roughgarden, editor, Beyond Worst Case Analysis of Algorithms . Cambridge University Press, 2020

    2020

  5. [5]

    Mechanism design via machine learning

    Maria-Florina Balcan, Avrim Blum, Jason D Hartline, and Yishay Mansour. Mechanism design via machine learning. In Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS), pages 605–614, 2005

    2005

  6. [6]

    Sample complexity of auto- mated mechanism design

    Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik. Sample complexity of auto- mated mechanism design. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), 2016

    2016

  7. [7]

    Learning- theoretic foundations of algorithm configuration for combinatorial partitioning problems

    Maria-Florina Balcan, Vaishnavh Nagarajan, Ellen Vitercik, and Colin White. Learning- theoretic foundations of algorithm configuration for combinatorial partitioning problems. Conference on Learning Theory (COLT), 2017

    2017

  8. [8]

    Learning to branch

    Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, and Ellen Vitercik. Learning to branch. International Conference on Machine Learning (ICML) , 2018

    2018

Show all 115 references
  1. [9]

    Dispersion for data-driven algorithm design, online learning, and private optimization

    Maria-Florina Balcan, Travis Dick, and Ellen Vitercik. Dispersion for data-driven algorithm design, online learning, and private optimization. In Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS) , 2018

    2018

  2. [10]

    A general theory of sample complexity for multi-item profit maximization

    Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik. A general theory of sample complexity for multi-item profit maximization. In Proceedings of the ACM Conference on Economics and Computation (EC) , 2018. Extended abstract. Full version available on arXiv with the same title

    2018

  3. [11]

    Learning to link

    Maria-Florina Balcan, Travis Dick, and Manuel Lang. Learning to link. In Proceedings of the International Conference on Learning Representations (ICLR) , 2020

    2020

  4. [12]

    Semi-bandit optimization in the dispersed setting

    Maria-Florina Balcan, Travis Dick, and Wesley Pegden. Semi-bandit optimization in the dispersed setting. In Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI), 2020

    2020

  5. [13]

    Learning to optimize com- putational resources: Frugal training with generalization guarantees

    Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik. Learning to optimize com- putational resources: Frugal training with generalization guarantees. AAAI Conference on Artificial Intelligence (AAAI) , 2020

    2020

  6. [14]

    Generalization in portfolio- based algorithm selection

    Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik. Generalization in portfolio- based algorithm selection. In AAAI Conference on Artificial Intelligence (AAAI) , 2021. 43

    2021

  7. [15]

    Some unexpected expected behavior results for bin packing

    Jon Louis Bentley, David S Johnson, Frank Thomson Leighton, Catherine C McGeoch, and Lyle A McGeoch. Some unexpected expected behavior results for bin packing. In Proceedings of the Annual Symposium on Theory of Computing (STOC) , pages 279–288, 1984

    1984

  8. [16]

    Maria-florina balcan and dan f

    Dimitris Bertsimas and Vassilis Digalakis Jr. Maria-florina balcan and dan f. deblasio and travis dick and carl kingsford and tuomas sandholm and ellen vitercik. arXiv preprint arXiv:1908.02894, 2019

    1908 arXiv

  9. [17]

    Learning complexity of simulated annealing

    Avrim Blum, Chen Dan, and Saeed Seddighin. Learning complexity of simulated annealing. In International Conference on Artificial Intelligence and Statistics (AISTATS) , 2021

    2021

  10. [18]

    Partition of space

    Robert Creighton Buck. Partition of space. The American Mathematical Monthly , 50:541– 544, 1943. ISSN 0002-9890

    1943

  11. [19]

    Learning multi-item auctions with (or without) samples

    Yang Cai and Constantinos Daskalakis. Learning multi-item auctions with (or without) samples. In Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS), 2017

    2017

  12. [20]

    Pandora’s box with correlations: Learning and approximation

    Shuchi Chawla, Evangelia Gergatsouli, Yifeng Teng, Christos Tzamos, and Ruimin Zhang. Pandora’s box with correlations: Learning and approximation. In Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS) , 2020

    2020

  13. [21]

    Learning to schedule heuristics in branch-and-bound

    Antonia Chmiela, Elias B Khalil, Ambros Gleixner, Andrea Lodi, and Sebastian Pokutta. Learning to schedule heuristics in branch-and-bound. arXiv preprint arXiv:2103.10294, 2021

    2021 arXiv

  14. [22]

    Ed H. Clarke. Multipart pricing of public goods. Public Choice, 11:17–33, 1971

    1971

  15. [23]

    The sample complexity of revenue maximization

    Richard Cole and Tim Roughgarden. The sample complexity of revenue maximization. In Proceedings of the Annual Symposium on Theory of Computing (STOC) , 2014

    2014

  16. [24]

    Parameter Advising for Multiple Sequence Alignment

    Dan DeBlasio and John D Kececioglu. Parameter Advising for Multiple Sequence Alignment . Springer, 2018

    2018

  17. [25]

    The sample complexity of auctions with side information

    Nikhil R Devanur, Zhiyi Huang, and Christos-Alexandros Psomas. The sample complexity of auctions with side information. In Proceedings of the Annual Symposium on Theory of Computing (STOC), 2016

    2016

  18. [26]

    Secretaries with advice

    Paul D¨ utting, Silvio Lattanzi, Renato Paes Leme, and Sergei Vassilvitskii. Secretaries with advice. arXiv preprint arXiv:2011.06726 , 2020

    2011 arXiv

  19. [27]

    Learning-based support estimation in sublinear time

    Talya Eden, Piotr Indyk, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, and Tal Wag- ner. Learning-based support estimation in sublinear time. In Proceedings of the International Conference on Learning Representations (ICLR), 2021

    2021

  20. [28]

    Quality measures for protein alignment benchmarks

    Robert C Edgar. Quality measures for protein alignment benchmarks. Nucleic acids research, 38(7):2145–2153, 2010

    2010

  21. [29]

    Designing and learning optimal finite support auctions

    Edith Elkind. Designing and learning optimal finite support auctions. In Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , 2007

    2007

  22. [30]

    Rein- forcement learning for variable selection in a branch and bound algorithm

    Marc Etheve, Zacharie Al` es, Cˆ ome Bissuel, Olivier Juan, and Safia Kedad-Sidhoum. Rein- forcement learning for variable selection in a branch and bound algorithm. pages 176–185. Springer, 2020. 44

    2020

  23. [31]

    Learning augmented energy minimization via speed scaling

    ´Etienne Bamas, Andreas Maggiori, Lars Rohwedder, and Ola Svensson. Learning augmented energy minimization via speed scaling. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS) , 2020

    2020

  24. [32]

    The primal-dual method for learn- ing augmented algorithms

    ´Etienne Bamas, Andreas Maggiori, and Ola Svensson. The primal-dual method for learn- ing augmented algorithms. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), 2020

    2020

  25. [33]

    The RPR 2 rounding technique for semidefinite programs

    Uriel Feige and Michael Langberg. The RPR 2 rounding technique for semidefinite programs. Journal of Algorithms , 60(1):1–23, 2006

    2006

  26. [34]

    Progressive sequence alignment as a prerequisite to correct phylogenetic trees

    Da-Fei Feng and Russell F Doolittle. Progressive sequence alignment as a prerequisite to correct phylogenetic trees. Journal of Molecular Evolution , 25(4):351–360, 1987

    1987

  27. [35]

    MIPaaL: Mixed integer program as a layer

    Aaron Ferber, Bryan Wilder, Bistra Dilkina, and Milind Tambe. MIPaaL: Mixed integer program as a layer. In AAAI Conference on Artificial Intelligence (AAAI) , volume 34, pages 1504–1511, 2020

    2020

  28. [36]

    Parametric multiple sequence alignment and phylogeny construction

    David Fern´ andez-Baca, Timo Sepp¨ al¨ ainen, and Giora Slutzki. Parametric multiple sequence alignment and phylogeny construction. Journal of Discrete Algorithms , 2(2):271–287, 2004

    2004

  29. [37]

    Identification of alternative topological domains in chromatin

    Darya Filippova, Rob Patro, Geet Duggal, and Carl Kingsford. Identification of alternative topological domains in chromatin. Algorithms for Molecular Biology , 9:14, May 2014

    2014

  30. [38]

    A machine learning- based branch and price algorithm for a sampled vehicle routing problem

    Nikolaus Furian, Michael O’Sullivan, Cameron Walker, and Eranda C ¸ ela. A machine learning- based branch and price algorithm for a sampled vehicle routing problem. OR Spectrum, pages 1–40, 2021

    2021

  31. [39]

    Supervising unsupervised learning

    Vikas Garg and Adam Kalai. Supervising unsupervised learning. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS) . 2018

    2018

  32. [40]

    Information-theoretic approaches to branching in search

    Andrew Gilpin and Tuomas Sandholm. Information-theoretic approaches to branching in search. Discrete Optimization, 8(2):147–159, 2011. Early version in IJCAI-07

    2011

  33. [41]

    Improved approximation algorithms for max- imum cut and satisfiability problems using semidefinite programming

    Michel X Goemans and David P Williamson. Improved approximation algorithms for max- imum cut and satisfiability problems using semidefinite programming. Journal of the ACM (JACM), 42(6):1115–1145, 1995

    1995

  34. [42]

    Eigentaste: A constant time collaborative filtering algorithm

    Ken Goldberg, Theresa Roeder, Dhruv Gupta, and Chris Perkins. Eigentaste: A constant time collaborative filtering algorithm. Information Retrieval, 4(2):133–151, 2001

    2001

  35. [43]

    Efficient empirical revenue maximization in single- parameter auction environments

    Yannai A Gonczarowski and Noam Nisan. Efficient empirical revenue maximization in single- parameter auction environments. In Proceedings of the Annual Symposium on Theory of Computing (STOC), pages 856–868, 2017

    2017

  36. [44]

    The sample complexity of up-to- ε multi- dimensional revenue maximization

    Yannai A Gonczarowski and S Matthew Weinberg. The sample complexity of up-to- ε multi- dimensional revenue maximization. Journal of the ACM , 68(3):1–28, 2021

    2021

  37. [45]

    An improved algorithm for matching biological sequences

    Osamu Gotoh. An improved algorithm for matching biological sequences. Journal of Molec- ular Biology, 162(3):705 – 708, 1982. ISSN 0022-2836

    1982

  38. [46]

    Incentives in teams

    Theodore Groves. Incentives in teams. Econometrica, 41:617–631, 1973. 45

    1973

  39. [47]

    Settling the sample complexity of single- parameter revenue maximization

    Chenghao Guo, Zhiyi Huang, and Xinzhi Zhang. Settling the sample complexity of single- parameter revenue maximization. Proceedings of the Annual Symposium on Theory of Com- puting (STOC), 2019

    2019

  40. [48]

    A PAC approach to application-specific algorithm se- lection

    Rishi Gupta and Tim Roughgarden. A PAC approach to application-specific algorithm se- lection. SIAM Journal on Computing , 46(3):992–1017, 2017

    2017

  41. [49]

    Parametric and inverse-parametric sequence alignment with xparal

    Dan Gusfield and Paul Stelling. Parametric and inverse-parametric sequence alignment with xparal. In Methods in enzymology, volume 266, pages 481–494. Elsevier, 1996

    1996

  42. [50]

    Parametric optimization of se- quence alignment

    Dan Gusfield, Krishnan Balasubramanian, and Dalit Naor. Parametric optimization of se- quence alignment. Algorithmica, 12(4-5):312–326, 1994

    1994

  43. [51]

    Clustal: a package for performing multiple sequence alignment on a microcomputer

    Desmond G Higgins and Paul M Sharp. Clustal: a package for performing multiple sequence alignment on a microcomputer. Gene, 73(1):237–244, 1988

    1988

  44. [52]

    Holley, Jean Apgar, George A

    Robert W. Holley, Jean Apgar, George A. Everett, James T. Madison, Mark Marquisee, Susan H. Merrill, John Robert Penswick, and Ada Zamir. Structure of a ribonucleic acid. Science, 147(3664):1462–1465, 1965

    1965

  45. [53]

    A Bayesian approach to tackling hard computational problems

    Eric Horvitz, Yongshao Ruan, Carla Gomez, Henry Kautz, Bart Selman, and Max Chicker- ing. A Bayesian approach to tackling hard computational problems. In Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI) , 2001

    2001

  46. [54]

    Learning-based frequency estima- tion algorithms

    Chen-Yu Hsu, Piotr Indyk, Dina Katabi, and Ali Vakilian. Learning-based frequency estima- tion algorithms. In Proceedings of the International Conference on Learning Representations (ICLR), 2019

    2019

  47. [55]

    ParamILS: An auto- matic algorithm configuration framework

    Frank Hutter, Holger Hoos, Kevin Leyton-Brown, and Thomas St¨ utzle. ParamILS: An auto- matic algorithm configuration framework. Journal of Artificial Intelligence Research , 36(1): 267–306, 2009. ISSN 1076-9757

    2009

  48. [56]

    Online page migration with ml advice

    Piotr Indyk, Frederik Mallmann-Trenn, Slobodan Mitrovi´ c, and Ronitt Rubinfeld. Online page migration with ml advice. arXiv preprint arXiv:2006.05028 , 2020

    2006 arXiv

  49. [57]

    An experimental study of polylogarithmic, fully dynamic, connectivity algorithms

    Raj Iyer, David Karger, Hariharan Rahul, and Mikkel Thorup. An experimental study of polylogarithmic, fully dynamic, connectivity algorithms. ACM Journal of Experimental Al- gorithmics, 6:4–es, December 2002. ISSN 1084-6654

    2002

  50. [58]

    ISAC-instance-specific algorithm configuration

    Serdar Kadioglu, Yuri Malitsky, Meinolf Sellmann, and Kevin Tierney. ISAC-instance-specific algorithm configuration. In Proceedings of the European Conference on Artificial Intelligence (ECAI), 2010

    2010

  51. [59]

    Aligning alignments exactly

    John D Kececioglu and Dean Starrett. Aligning alignments exactly. In Proceedings of the Annual International Conference on Computational Molecular Biology, RECOMB , volume 8, pages 85–96, 2004

    2004

  52. [60]

    Inverse sequence alignment from partial examples

    Eagu Kim and John Kececioglu. Inverse sequence alignment from partial examples. Proceed- ings of the International Workshop on Algorithms in Bioinformatics , pages 359–370, 2007

    2007

  53. [61]

    Efficiency through procrastina- tion: Approximately optimal algorithm configuration with runtime guarantees

    Robert Kleinberg, Kevin Leyton-Brown, and Brendan Lucier. Efficiency through procrastina- tion: Approximately optimal algorithm configuration with runtime guarantees. InProceedings of the International Joint Conference on Artificial Intelligence (IJCAI) , 2017. 46

    2017

  54. [62]

    Procrastinat- ing with confidence: Near-optimal, anytime, adaptive algorithm configuration

    Robert Kleinberg, Kevin Leyton-Brown, Brendan Lucier, and Devon Graham. Procrastinat- ing with confidence: Near-optimal, anytime, adaptive algorithm configuration. Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS) , 2019

    2019

  55. [63]

    End-to-end constrained optimization learning: A survey

    James Kotary, Ferdinando Fioretto, Pascal Van Hentenryck, and Bryan Wilder. End-to-end constrained optimization learning: A survey. arXiv preprint arXiv:2103.16378 , 2021

    2021 arXiv

  56. [64]

    An automatic method of solving discrete programming problems

    Ailsa H Land and Alison G Doig. An automatic method of solving discrete programming problems. Econometrica: Journal of the Econometric Society , pages 497–520, 1960

    1960

  57. [65]

    Learnable and instance-robust predictions for online matching, flows and load balancing

    Thomas Lavastida, Benjamin Moseley, R Ravi, and Chenyang Xu. Learnable and instance-robust predictions for online matching, flows and load balancing. arXiv preprint arXiv:2011.11743, 2020

    2011 arXiv

  58. [66]

    Empirical hardness models: Methodology and a case study on combinatorial auctions

    Kevin Leyton-Brown, Eugene Nudelman, and Yoav Shoham. Empirical hardness models: Methodology and a case study on combinatorial auctions. Journal of the ACM , 56(4):1–52,

  59. [67]

    van Berkum, Louise Williams, Maxim Imakaev, Tobias Ragoczy, Agnes Telling, Ido Amit, Bryan R

    Erez Lieberman-Aiden, Nynke L. van Berkum, Louise Williams, Maxim Imakaev, Tobias Ragoczy, Agnes Telling, Ido Amit, Bryan R. Lajoie, Peter J. Sabo, Michael O. Dorschner, Richard Sandstrom, Bradley Bernstein, M. A. Bender, Mark Groudine, Andreas Gnirke, John Stamatoyannopoulos,...

    2009 doi

  60. [68]

    Methods for boosting revenue in combinatorial auctions

    Anton Likhodedov and Tuomas Sandholm. Methods for boosting revenue in combinatorial auctions. In Proceedings of the National Conference on Artificial Intelligence (AAAI) , pages 232–237, San Jose, CA, 2004

    2004

  61. [69]

    Approximating revenue-maximizing combinato- rial auctions

    Anton Likhodedov and Tuomas Sandholm. Approximating revenue-maximizing combinato- rial auctions. In Proceedings of the National Conference on Artificial Intelligence (AAAI) , Pittsburgh, PA, 2005

    2005

  62. [70]

    A computational study of search strategies for mixed integer programming

    Jeff Linderoth and Martin Savelsbergh. A computational study of search strategies for mixed integer programming. INFORMS Journal of Computing , 11:173–187, 1999

    1999

  63. [71]

    Breaking TADs: how alterations of chromatin domains result in disease

    Dar´ ıo G Lupi´ a˜ nez, Malte Spielmann, and Stefan Mundlos. Breaking TADs: how alterations of chromatin domains result in disease. Trends in Genetics, 32(4):225–237, 2016

    2016

  64. [72]

    Competitive caching with machine learned advice

    Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice. In International Conference on Machine Learning (ICML) , 2018

    2018

  65. [73]

    A guide to experimental algorithmics

    Catherine C McGeoch. A guide to experimental algorithmics . Cambridge University Press, 2012

    2012

  66. [74]

    Roberts’ theorem with neutrality: A social welfare ordering approach

    Debasis Mishra and Arunava Sen. Roberts’ theorem with neutrality: A social welfare ordering approach. Games and Economic Behavior , 75(1):283–298, 2012

    2012

  67. [75]

    A model for learned bloom filters and optimizing by sandwiching

    Michael Mitzenmacher. A model for learned bloom filters and optimizing by sandwiching. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), pages 464–473, 2018. 47

    2018

  68. [76]

    Learning theory and algorithms for revenue optimization in second price auctions with reserve

    Mehryar Mohri and Andr´ es Mu˜ noz. Learning theory and algorithms for revenue optimization in second price auctions with reserve. In International Conference on Machine Learning (ICML), 2014

    2014

  69. [77]

    Learning simple auctions

    Jamie Morgenstern and Tim Roughgarden. Learning simple auctions. In Conference on Learning Theory (COLT), 2016

    2016

  70. [78]

    Efficiency and budget balance in general quasi-linear domains

    Swaprava Nath and Tuomas Sandholm. Efficiency and budget balance in general quasi-linear domains. Games and Economic Behavior , 113:673 – 693, 2019

    2019

  71. [79]

    Finding biologically accurate clusterings in hierarchical tree decompositions using the variation of information

    Saket Navlakha, James White, Niranjan Nagarajan, Mihai Pop, and Carl Kingsford. Finding biologically accurate clusterings in hierarchical tree decompositions using the variation of information. In Annual International Conference on Research in Computational Molecular Biology, ...

    2009

  72. [80]

    Fast algorithm for predicting the secondary structure of single-stranded RNA

    Ruth Nussinov and Ann B Jacobson. Fast algorithm for predicting the secondary structure of single-stranded RNA. Proceedings of the National Academy of Sciences, 77(11):6309–6313, 1980

    1980

  73. [81]

    Parametric inference for biological sequence analysis

    Lior Pachter and Bernd Sturmfels. Parametric inference for biological sequence analysis. Proceedings of the National Academy of Sciences , 101(46):16138–16143, 2004. doi: 10.1073/ pnas.0406011101

    2004

  74. [82]

    Tropical geometry of statistical models

    Lior Pachter and Bernd Sturmfels. Tropical geometry of statistical models. Proceedings of the National Academy of Sciences , 101(46):16132–16137, 2004. doi: 10.1073/pnas.0406010101

    2004 doi

  75. [83]

    Convergence of Stochastic Processes

    David Pollard. Convergence of Stochastic Processes. Springer, 1984

    1984

  76. [84]

    Ecole: A gym-like library for machine learning in combinatorial optimization solvers

    Antoine Prouvost, Justin Dumouchelle, Lara Scavuzzo, Maxime Gasse, Didier Ch´ etelat, and Andrea Lodi. Ecole: A gym-like library for machine learning in combinatorial optimization solvers. arXiv preprint arXiv:2011.06069 , 2020

    2011 arXiv

  77. [85]

    Improving online algorithms via ML pre- dictions

    Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ML pre- dictions. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), pages 9661–9670, 2018

    2018

  78. [86]

    The characterization of implementable social choice rules

    Kevin Roberts. The characterization of implementable social choice rules. In J-J Laffont, editor, Aggregation and Revelation of Preferences. North-Holland Publishing Company, 1979

    1979

  79. [87]

    Very-large-scale generalized combinatorial multi-attribute auctions: Lessons from conducting $60 billion of sourcing

    Tuomas Sandholm. Very-large-scale generalized combinatorial multi-attribute auctions: Lessons from conducting $60 billion of sourcing. In Zvika Neeman, Alvin Roth, and Nir Vulkan, editors, Handbook of Market Design . Oxford University Press, 2013

    2013

  80. [88]

    Automated design of revenue-maximizing com- binatorial auctions

    Tuomas Sandholm and Anton Likhodedov. Automated design of revenue-maximizing com- binatorial auctions. Operations Research, 63(5):1000–1025, 2015. Special issue on Computa- tional Economics. Subsumes and extends over a AAAI-05 paper and a AAAI-04 paper

    2015

  81. [89]

    Michael Sauder, Jonathan W

    J. Michael Sauder, Jonathan W. Arthur, and Roland L. Dunbrack Jr. Large-scale comparison of protein sequence alignment algorithms with structure alignments. Proteins: Structure, Function, and Bioinformatics , 40(1):6–22, 2000

    2000

  82. [90]

    On the density of families of sets

    Norbert Sauer. On the density of families of sets. Journal of Combinatorial Theory, Series A, 13(1):145–147, 1972. 48

    1972

  83. [91]

    Guiding high-performance SAT solvers with unsat-core predictions

    Daniel Selsam and Nikolaj Bjørner. Guiding high-performance SAT solvers with unsat-core predictions. In International Conference on Theory and Applications of Satisfiability Testing , pages 336–353. Springer, 2019

    2019

  84. [92]

    Understanding machine learning: From theory to algorithms

    Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge University Press, 2014

    2014

  85. [93]

    Lorm: Learning to optimize for resource management in wireless networks with few training samples

    Yifei Shen, Yuanming Shi, Jun Zhang, and Khaled B Letaief. Lorm: Learning to optimize for resource management in wireless networks with few training samples. IEEE Transactions on Wireless Communications, 19(1):665–679, 2019

    2019

  86. [94]

    A general large neighborhood search framework for solving integer programs

    Jialin Song, Ravi Lanka, Yisong Yue, and Bistra Dilkina. A general large neighborhood search framework for solving integer programs. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS) , 2020

    2020

  87. [95]

    Reinforcement learning for integer program- ming: Learning to cut

    Yunhao Tang, Shipra Agrawal, and Yuri Faenza. Reinforcement learning for integer program- ming: Learning to cut. In International Conference on Machine Learning (ICML) , 2020

    2020

  88. [96]

    On the zeros of finite sums of exponential functions

    Timo Tossavainen. On the zeros of finite sums of exponential functions. Australian Mathe- matical Society Gazette, 33(1):47–50, 2006

    2006

  89. [97]

    On the uniform convergence of relative frequencies of events to their probabilities

    Vladimir Vapnik and Alexey Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications , 16(2):264–280, 1971

    1971

  90. [98]

    Counterspeculation, auctions, and competitive sealed tenders

    William Vickrey. Counterspeculation, auctions, and competitive sealed tenders. Journal of Finance, 16:8–37, 1961

    1961

  91. [99]

    On the complexity of multiple sequence alignment

    Lusheng Wang and Tao Jiang. On the complexity of multiple sequence alignment. Journal of Computational Biology , 1(4):337–348, 1994

    1994

  92. [100]

    Some biological sequence metrics

    Michael S Waterman, Temple F Smith, and William A Beyer. Some biological sequence metrics. Advances in Mathematics, 20(3):367–387, 1976

    1976

  93. [101]

    Learning variable ordering heuristics with multi-armed bandits and restarts

    Hugues Wattez, Fr´ ed´ eric Koriche, Christophe Lecoutre, Anastasia Paparrizou, and S´ ebastien Tabary. Learning variable ordering heuristics with multi-armed bandits and restarts. 2020

    2020

  94. [102]

    Optimal robustness-consistency trade-offs for learning- augmented online algorithms

    Alexander Wei and Fred Zhang. Optimal robustness-consistency trade-offs for learning- augmented online algorithms. In Proceedings of the Annual Conference on Neural Information Processing Systems (NeurIPS), 2020

    2020

  95. [103]

    In International Conference on Machine Learning (ICML), 2018

    Gell´ ert Weisz, Andr´ as Gy¨ orgy, and Csaba Szepesv´ ari.LeapsAndBounds: A method for approximately optimal algorithm configuration. In International Conference on Machine Learning (ICML), 2018

    2018

  96. [104]

    In International Conference on Machine Learning (ICML), 2019

    Gell´ ert Weisz, Andr´ as Gy¨ orgy, and Csaba Szepesv´ ari.CapsAndRuns: An improved method for approximately optimal algorithm configuration. In International Conference on Machine Learning (ICML), 2019

    2019

  97. [105]

    Wheeler and John D

    Travis J. Wheeler and John D. Kececioglu. Multiple alignment by aligning alignments. Bioin- formatics, 23(13):i559–i568, 07 2007

    2007

  98. [106]

    SATzilla: portfolio-based algorithm selection for SAT

    Lin Xu, Frank Hutter, Holger H Hoos, and Kevin Leyton-Brown. SATzilla: portfolio-based algorithm selection for SAT. Journal of Artificial Intelligence Research , 32(1):565–606, 2008. 49

    2008

  99. [107]

    Hydra-MIP: Automated algorithm configuration and selection for mixed integer programming

    Lin Xu, Frank Hutter, Holger H Hoos, and Kevin Leyton-Brown. Hydra-MIP: Automated algorithm configuration and selection for mixed integer programming. In RCRA workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion at the Internationa...

    2011

  100. [108]

    Parameterizing branch-and- bound search trees to learn branching policies

    Giulia Zarpellon, Jason Jo, Andrea Lodi, and Yoshua Bengio. Parameterizing branch-and- bound search trees to learn branching policies. In AAAI Conference on Artificial Intelligence (AAAI), 2021. A Helpful lemmas Lemma A.1 (Shalev-Shwartz and Ben-David [92]) . Let a≥ 1 and b >0....

    2021

  101. [109]

    A set of N = Θ(logn) sequence pairs ( S(1) 1 ,S (1) 2 ) ,..., ( S(N) 1 ,S (N) 2 ) ∈∪ n i=1Σi× Σi,

  102. [110]

    A ground-truth alignment L(i) ∗ for each sequence pair ( S(i) 1 ,S (i) 2 ) , and

  103. [111]

    We now describe each of these four elements in turn

    A set of N witnesses z1,...,z N∈ R such that for any subset T⊆ [N], there exists an indel penalty parameter ρ[T ] such that if i∈ [T ], then u0,ρ[T ],0 ( S(i) 1 ,S (i) 2 ) <z i and if i⁄∈ [T ], then u0,ρ[T ],0 ( S(i) 1 ,S (i) 2 ) ≥zi. We now describe each of these four element...

  104. [112]

    Claim C.3

    To prove this, we will use two helpful claims, Claims C.3 and C.4. Claim C.3. For any pair ( S(i) 1 ,S (i) 2 ) and indel parameter ρ[2]≥ 0, there exists an alignment L∈ argmaxL′mt ( S(i) 1 ,S (i) 2 ,L′ ) −ρ[2]· id ( S(i) 1 ,S (i) 2 ,L′ ) such that each dj character in S(i) 1 i...

  105. [113]

    After all, for every i∈{ 2,...,N } and every interval ( 1 2(k+1)−j2i, 1 2(k+1)−(j+1)2i ) where u0,ρ[2],0 ( S(i) 1 ,S (i) 2 ) is uniformly above or below 3 4, there exists a subpartition of this interval into the two intervals ( 1 2(k + 1)−j2i, 1 2(k + 1)− (2j + 1)2i−1 ) and ( ...

  106. [114]

    Therefore, for any subset T ⊆ [N], there exists an indel penalty parameter ρ[T ] such that if i∈ [T ], then u0,ρ[T ],0 ( S(i) 1 ,S (i) 2 ) < 3 4 and if i⁄∈ [T ], then u0,ρ[T ],0 ( S(i) 1 ,S (i) 2 ) > 3 4. C.1 Tighter guarantees for a structured algorithm subclass: sequence ali...

  107. [115]

    Figure 10a depicts a completed guide tree

    be the alignment sequences computed at vi Let c1 and c2 be the children of vi Set σc1 =σc2 = “” Set k = 0 for j∈ [|σvi|] do if σvi[j] = ‘-’ then Append ‘-’ to the end of both σc1 and σc2 else Append τ′ 1[k] to the end of σc1 Append τ′ 2[k] to the end of σc2 Incrementk by 1 for...

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.