Algorithm design

By Robert Endre Tarjan. 1987

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Learning Combinatorial Optimization Algorithms over Graphs (2017, methodology): “• MAXCUT: We include MaxcutApprox , which maintains the cut set ( S, V \ S ) and moves a node from one side to the other side of the cut if that operation results in cut weight improvement [25].”
Faith and Fate: Limits of Transformers on Compositionality (2023, methodology): “We analyze a classic relaxation of the NP-complete Maximum Weighted Independent Set problem [39]: Given a sequence of integers, find a subsequence with the highest sum, such that no two numbers in the subsequence are adjacent in the original sequence .”
The Design of Approximation Algorithms (2011, methodology): “Many books on algorithms and combinatorial optimization now contain sections on approximation algorithms, including the textbooks of Bertsimas and Tsitsiklis [47], Cook, Cunningham, Pulleyblank, and Schrijver [81], Cormen, Leiserson, Rivest, and Stein [82], Kleinberg and Tardos [198], and Korte and ”
Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth (2013, methodology): “See [14,20] for sample applications to the Independent Set / Vertex Cover problems.”
Proof-of-Stake Consensus Mechanisms for Future Blockchain Networks: Fundamentals, Applications and Opportunities (2019, background): “Formally, the worst-case time complexity of Algorithm 1 is O(Nη ), where η is the input size [52].”
Gradient Estimation with Stochastic Softmax Tricks (2020, background): “Algorithm 1: Maximum r -arborescence [39] Init: graph G , node r , U e ∈ R , T = ∅ ; ∈ ∪ { T is an arborescence then return x T ; 6 else there is a directed cycle C ⊆ T form 2 is an equivalent categorical sampling process for X .”
Video Object Segmentation through Spatially Accurate and Temporally Dense Extraction of Primary Object Regions (2013, background): “This problem could be solved by dynamic programming in linear time [12].”
Learning a Local-Variable Model of Aromatic and Conjugated Systems (2018, background): “54 For tree edges, one atom of the edge is updated ﬁ rst, and then its updated state is sent to the next atom.”
The Algorithm Design Manual (2020, unknown): “al [CLRS01], Kleinberg/Tardos [KT06], and Manber [Man89].”
Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time (2011, background): “(1) time algorithms, where tw is the treewidth of the input graphG = (V ,E) and c is a constant.”
Proportional Fair Frequency-Domain Packet Scheduling for 3GPP LTE Uplink (2009, background): “The problem asks whether a directed graph G contains a hamiltonian path, and this is NP-complete [16].”
Practical verified computation with streaming interactive proofs (2011, background): “The convolution is the inverse transform of the inner product of the two transforms [23, Chapter 5].”
Models and Algorithms for Optimal Piecewise-Linear Function Approximation (2015, methodology): “For an introduction to dynamic programming in discrete domains, the interested reader can refer to the text books by Kleinberg and Tardos [10] and Cormen et al. [11].”