On the public citation graph

Randomized competitive algorithms for the list update problem

0 signed · 111 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.

Claim with ORCID

Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.

See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1007/bf01188711openalex-snapshot

Fast linear expected-time algorithms for computing maxima and convex hulls

inferredcites →https://doi.org/10.1007/bf01762111openalex-snapshot

Competitive snoopy caching

inferredcites →https://doi.org/10.1007/bfb0035792openalex-snapshot

Memory versus randomization in on-line algorithms

inferredcites →https://doi.org/10.1016/0020-0190(91)90086-wopenalex-snapshot

Two results on the list update problem

inferredcites →https://doi.org/10.1016/0196-6774(91)90035-wopenalex-snapshot

On fast algorithms for two servers

inferredcites →https://doi.org/10.1016/0196-6774(91)90041-vopenalex-snapshot

Competitive paging algorithms

inferredcites →https://doi.org/10.1017/s0021900200118595openalex-snapshot

On a model for storage and search

inferredcites →https://doi.org/10.1090/dimacs/007/10openalex-snapshot

Randomized algorithms for multiprocessor page migration

inferredcites →https://doi.org/10.1137/0205050openalex-snapshot

An Account of Self-Organizing Systems

inferredcites →https://doi.org/10.1137/s0097539791199796openalex-snapshot

Randomized Algorithms for Multiprocessor Page Migration

inferredcites →https://doi.org/10.1145/100216.100266openalex-snapshot

Random walks on weighted graphs, and applications to on-line algorithms

inferredcites →https://doi.org/10.1145/100216.100268openalex-snapshot

On the power of randomization in online algorithms

inferredcites →https://doi.org/10.1145/2786.2793openalex-snapshot

Amortized efficiency of list update and paging rules

inferredcites →https://doi.org/10.1145/28395.28435openalex-snapshot

An optimal online algorithm for metrical task systems

inferredcites →https://doi.org/10.1145/3341.3349openalex-snapshot

Amortized analyses of self-organizing sequential search heuristics

inferredcites →https://doi.org/10.1145/359997.360000openalex-snapshot

On self-organizing sequential search heuristics

inferredcites →https://doi.org/10.1145/5684.5688openalex-snapshot

A locally adaptive data compression scheme

inferredcites →https://doi.org/10.1145/62212.62243openalex-snapshot

Competitive algorithms for on-line problems

inferredcites →https://doi.org/10.1147/rd.386.0683openalex-snapshot

Memory versus randomization in on-line algorithms

inferredcites →https://doi.org/10.1184/r1/6604253openalex-snapshot

Competitive algorithms for replication and migration problems

inferredcites →https://doi.org/10.1287/opre.13.4.609openalex-snapshot

On Serial Files with Relocatable Records

inferredcites →https://doi.org/10.2307/2003277openalex-snapshot

Elementary Numerical Analysis: An Algorithmic Approach

inferredcites →https://doi.org/10.5555/320176.320196openalex-snapshot

Fast linear expected-time alogorithms for computing maxima and convex hulls

inferredcites →https://doi.org/10.5555/320176.320216openalex-snapshot

Competitive randomized algorithms for non-uniform problems

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1006/inco.2001.3057openalex-snapshot

Delayed Information and Action in On-Line Algorithms

inferred← citeshttps://doi.org/10.1007/11764298_10openalex-snapshot

Lists on Lists: A Framework for Self-organizing Lists in Environments with Locality of Reference

inferred← citeshttps://doi.org/10.1007/3-540-34874-3_7openalex-snapshot

Online Algorithms

inferred← citeshttps://doi.org/10.1007/3-540-45022-x_27openalex-snapshot

Optimal Projective Algorithms for the List Update Problem

inferred← citeshttps://doi.org/10.1007/3-540-45253-2_5openalex-snapshot

Offline List Update is NP-hard

inferred← citeshttps://doi.org/10.1007/3-540-46784-x_2openalex-snapshot

Online Algorithms: A Study of Graph-Theoretic Concepts

inferred← citeshttps://doi.org/10.1007/3-540-48777-8_29openalex-snapshot

Scheduling Two Machines with Release Times

inferred← citeshttps://doi.org/10.1007/3-540-57568-5_274openalex-snapshot

Randomized competitive algorithms for successful and unsuccessful search on self-adjusting linear lists

inferred← citeshttps://doi.org/10.1007/3-540-61440-0_155openalex-snapshot

Average case analyses of list update algorithms, with applications to data compression

inferred← citeshttps://doi.org/10.1007/3-540-63397-9_16openalex-snapshot

A new family of randomized algorithms for list accessing

inferred← citeshttps://doi.org/10.1007/978-0-387-30162-4_266openalex-snapshot

Online List Update

inferred← citeshttps://doi.org/10.1007/978-0-387-30162-4_378openalex-snapshot

Ski Rental Problem

inferred← citeshttps://doi.org/10.1007/978-1-4939-2864-4_266openalex-snapshot

Online List Update

inferred← citeshttps://doi.org/10.1007/978-1-4939-2864-4_378openalex-snapshot

Ski Rental Problem

inferred← citeshttps://doi.org/10.1007/978-3-030-24922-9_23openalex-snapshot

Self-adjusting Linear Networks

inferred← citeshttps://doi.org/10.1007/978-3-030-34992-9_29openalex-snapshot

Self-adjusting Linear Networks

inferred← citeshttps://doi.org/10.1007/978-3-319-04921-2_17openalex-snapshot

On the List Update Problem with Advice

inferred← citeshttps://doi.org/10.1007/978-3-319-25258-2_7openalex-snapshot

A Randomized Algorithm for Online Scheduling with Interval Conflicts

inferred← citeshttps://doi.org/10.1007/978-3-540-27836-8_32openalex-snapshot

Online Scheduling of Equal-Length Jobs: Randomization and Restarts Help

inferred← citeshttps://doi.org/10.1007/978-3-540-70575-8_9openalex-snapshot

On List Update with Locality of Reference

inferred← citeshttps://doi.org/10.1007/978-3-540-74456-6_61openalex-snapshot

Online and Offline Access to Short Lists

inferred← citeshttps://doi.org/10.1007/978-3-540-77891-2_2openalex-snapshot

Closing the Gap Between Theory and Practice: New Measures for On-Line Algorithm Analysis

inferred← citeshttps://doi.org/10.1007/978-3-540-78773-0_35openalex-snapshot

List Update with Locality of Reference

inferred← citeshttps://doi.org/10.1007/978-3-540-87744-8_14openalex-snapshot

Randomized Competitive Analysis for Two-Server Problems

inferred← citeshttps://doi.org/10.1007/978-3-642-12450-1_10openalex-snapshot

Parameterized Analysis of Paging and List Update Algorithms

inferred← citeshttps://doi.org/10.1007/978-3-642-18318-8_11openalex-snapshot

List Factoring and Relative Worst Order Analysis

inferred← citeshttps://doi.org/10.1007/978-3-642-18381-2_28openalex-snapshot

Advice Complexity and Barely Random Algorithms

inferred← citeshttps://doi.org/10.1007/978-3-642-27848-8_266-2openalex-snapshot

Online List Update

inferred← citeshttps://doi.org/10.1007/978-3-642-27848-8_378-2openalex-snapshot

Ski Rental Problem

inferred← citeshttps://doi.org/10.1007/978-3-642-29116-6_13openalex-snapshot

A New Perspective on List Update: Probabilistic Locality and Working Set

inferred← citeshttps://doi.org/10.1007/978-3-642-40273-9_17openalex-snapshot

A Survey of Algorithms and Models for List Update

inferred← citeshttps://doi.org/10.1007/978-3-662-62223-0_2openalex-snapshot

Resource Planning

inferred← citeshttps://doi.org/10.1007/978-3-662-62223-0_5openalex-snapshot

Scheduling in Lagern

inferred← citeshttps://doi.org/10.1007/bfb0029563openalex-snapshot

Self-organizing data structures

inferred← citeshttps://doi.org/10.1007/pl00009217openalex-snapshot

Average Case Analyses of List Update Algorithms, with Applications to Data Compression

inferred← citeshttps://doi.org/10.1007/s00453-001-0069-8openalex-snapshot

On the Competitive Theory and Practice of Online List Accessing Algorithms

inferred← citeshttps://doi.org/10.1007/s00453-012-9637-3openalex-snapshot

List Factoring and Relative Worst Order Analysis

inferred← citeshttps://doi.org/10.1007/s00453-013-9800-5openalex-snapshot

Parameterized Analysis of Paging and List Update Algorithms

inferred← citeshttps://doi.org/10.1007/s00453-017-0393-2openalex-snapshot

Comparison-Based Buffer Management in QoS Switches

inferred← citeshttps://doi.org/10.1007/s00453-018-0461-2openalex-snapshot

On the Separation and Equivalence of Paging Strategies and Other Online Algorithms

inferred← citeshttps://doi.org/10.1007/s10107-003-0436-0openalex-snapshot

Online algorithms: a survey

inferred← citeshttps://doi.org/10.1007/s10479-025-06804-4openalex-snapshot

Randomized algorithms for fully online multiprocessor scheduling with testing

inferred← citeshttps://doi.org/10.1016/0020-0190(95)00142-yopenalex-snapshot

A combined BIT and TIMESTAMP algorithm for the list update problem

inferred← citeshttps://doi.org/10.1016/0304-3975(93)90201-4openalex-snapshot

The weighted list update problem and the lazy adversary

inferred← citeshttps://doi.org/10.1016/j.ic.2016.06.007openalex-snapshot

On the list update problem with advice

inferred← citeshttps://doi.org/10.1016/j.ic.2023.105038openalex-snapshot

Self-adjusting grid networks

inferred← citeshttps://doi.org/10.1016/j.ipl.2012.04.002openalex-snapshot

List update with probabilistic locality of reference

inferred← citeshttps://doi.org/10.1016/j.jcss.2015.11.005openalex-snapshot

On list update with locality of reference

inferred← citeshttps://doi.org/10.1016/j.tcs.2020.01.031openalex-snapshot

Paid exchanges are worth the price

inferred← citeshttps://doi.org/10.1016/s0020-0190(96)00144-5openalex-snapshot

Off-line algorithms for the list update problem

inferred← citeshttps://doi.org/10.1016/s0020-0190(97)00160-9openalex-snapshot

Revisiting the COUNTER algorithms for list update

inferred← citeshttps://doi.org/10.1016/s0167-6377(00)00053-5openalex-snapshot

Semi-online scheduling with decreasing job sizes

inferred← citeshttps://doi.org/10.1016/s0167-6377(98)00019-4openalex-snapshot

Randomized online interval scheduling

inferred← citeshttps://doi.org/10.1016/s0304-3975(00)00257-7openalex-snapshot

A new lower bound for the list update problem in the partial cost model

inferred← citeshttps://doi.org/10.1016/s0304-3975(00)00264-4openalex-snapshot

An optimal online algorithm for scheduling two machines with release times

inferred← citeshttps://doi.org/10.1016/s0304-3975(01)00078-0openalex-snapshot

A manifesto for the computational method

inferred← citeshttps://doi.org/10.1016/s0304-3975(97)00026-1openalex-snapshot

A competitive analysis of the list update problem with lookahead

inferred← citeshttps://doi.org/10.1016/s0304-3975(98)00264-3openalex-snapshot

On the competitiveness of the move-to-front rule

inferred← citeshttps://doi.org/10.1023/a:1022960526107openalex-snapshot

Barely Random Algorithms for Multiprocessor Scheduling

inferred← citeshttps://doi.org/10.1051/ita/2011105openalex-snapshot

Advice Complexity and Barely Random Algorithms

inferred← citeshttps://doi.org/10.1093/comjnl/bxl067openalex-snapshot

A Novel Framework for Self-Organizing Lists in Environments with Locality of Reference: Lists-on-Lists

inferred← citeshttps://doi.org/10.1109/2575-8411.2026.00060openalex-snapshot

Online Graph Embedding in Star Graphs

inferred← citeshttps://doi.org/10.1109/icdcs54860.2022.00016openalex-snapshot

Deterministic Self-Adjusting Tree Networks Using Rotor Walks

inferred← citeshttps://doi.org/10.1109/icgciot.2018.8753061openalex-snapshot

Characterization and Performance Evaluation of Request Sequence for Move-To-Front Algorithm

inferred← citeshttps://doi.org/10.1109/infocom48880.2022.9796885openalex-snapshot

Lazy Self-Adjusting Bounded-Degree Networks for the Matching Model

inferred← citeshttps://doi.org/10.1109/infocom53939.2023.10228937openalex-snapshot

Self-Adjusting Partially Ordered Lists

inferred← citeshttps://doi.org/10.1109/infocom53939.2023.10228999openalex-snapshot

SeedTree: A Dynamically Optimal and Local Self-Adjusting Tree

inferred← citeshttps://doi.org/10.1109/sccc.2002.1173169openalex-snapshot

Approximate and on-line algorithms for list update problem

inferred← citeshttps://doi.org/10.1137/s0097539704446608openalex-snapshot

Online Scheduling of Equal‐Length Jobs: Randomization and Restarts Help

inferred← citeshttps://doi.org/10.1137/s0097539791199796openalex-snapshot

Randomized Algorithms for Multiprocessor Page Migration

inferred← citeshttps://doi.org/10.1137/s0097539794277858openalex-snapshot

Improved Randomized On-Line Algorithms for the List Update Problem

inferred← citeshttps://doi.org/10.1137/s0097539795287824openalex-snapshot

Competitive On-Line Algorithms for Distributed Data Management

inferred← citeshttps://doi.org/10.1145/1711475.1711499openalex-snapshot

Introduction to the SIGACT news online algorithms column

inferred← citeshttps://doi.org/10.1145/1711475.1714372openalex-snapshot

On Developing New Models, with Paging as a Case Study

inferred← citeshttps://doi.org/10.1145/2500120openalex-snapshot

Optimal lower bounds for projective list update algorithms

inferred← citeshttps://doi.org/10.1145/3138860.3138871openalex-snapshot

SIGACT News Online Algorithms Column 31

inferred← citeshttps://doi.org/10.1145/3409964.3461824openalex-snapshot

Toward Self-Adjusting Networks for the Matching Model

inferred← citeshttps://doi.org/10.1145/3719027.3765149openalex-snapshot

Probabilistic Skipping-Based Data Structures with Robust Efficiency Guarantees

inferred← citeshttps://doi.org/10.22215/etd/2007-06291openalex-snapshot

Æip: a generalized framework for the study of interactive learning

inferred← citeshttps://doi.org/10.22215/etd/2007-08171openalex-snapshot

Adaptive admission control policy for web caching

inferred← citeshttps://doi.org/10.3390/a1010030openalex-snapshot

Randomized Competitive Analysis for Two Server Problems

inferred← citeshttps://doi.org/10.4230/dagsemproc.06421.4openalex-snapshot

Adaptive Analysis of On-line Algorithms

inferred← citeshttps://doi.org/10.48550/arxiv.1009.5787openalex-snapshot

List Factoring and Relative Worst Order Analysis

inferred← citeshttps://doi.org/10.48550/arxiv.1311.7357openalex-snapshot

On the List Update Problem with Advice

inferred← citeshttps://doi.org/10.48550/arxiv.1404.7638openalex-snapshot

An Optimal Offline Algorithm for List Update

inferred← citeshttps://doi.org/10.48550/arxiv.2109.15090openalex-snapshot

Self-Adjusting Packet Classification

inferred← citeshttps://doi.org/10.5555/314161.314180openalex-snapshot

Online list accessing algorithms and their applications: recent empirical evidence

Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.