NDLI: Can entropy characterize performance of online algorithms?

Please wait, while we are loading the content...

Combinatorial approximation algorithms for the maximum directed cut problem

Approximation algorithms for the 0-extension problem

A faster implementation of the Goemans-Williamson clustering algorithm

Tree packing and approximating k-cuts

Generating well-shaped Delaunay meshed in 3D

Approximation algorithms for TSP with neighborhoods in the plane

Dynamic skin triangulation

Online point location in planar arrangements and its applications

Reconciling simplicity and realism in parallel disk models

Distribution sort with randomized cycle

External memory BFS on undirected graphs with bounded degree

I/O-efficient algorithms for graphs of bounded treewidth

Constructing worst case instances for semidefinite programming based approximation algorithms

Randomizing combinatorial algorithms for linear programming when the dimension is moderately high

Approximation algorithms for the metric labeling problem via a new linear programming formulation

Lattice approximation and linear discrepency of totally unimodular matrices

On polynomial approximation to the shortest lattice vector length

Approximation for minimum triangulation of convex polyhedra

Optimal covering tours with turn costs

Maintaining approximate extent measures of moving points

Simplified kinetic connectivity for rectangles and hypercubes

Static and kinetic geometric spanners with applications

Gossip is synteny: incomplete gossip and an exact algorithm for syntenic distance

Absolute convergence: true trees from short sequences

Performance study of phylogenetic methods: (unweighted) quartet methods and neighbor-joining

A probabilistic analysis of a greedy algorithm arising from computational biology

On the midpath tree conjuncture: a counter-example

Distance labeling in graphs

Steiner points in tree metrics don't (really) help

Fast approximation of centrality

K-pair delay constrained minimum cost routing in undirected networks

A deterministic algorithm for the cost-distance problem

Shape sensitive geometric permutations

Geometric permutations of high dimensional spheres

Inserting an edge into a planar graph

Entropy-preserving cuttings and space-efficient planar point location

A simple entropy-based algorithm for planar point location

An experimental study of an opportunistic index

Overlap matching

A linear lower bound on index size for text retrieval

Pattern matching for sets of segments

Approximate subset matching with Don't Cares

Dynamic string searching

On approximating the achromatic number

Coloring k-colorable graphs using smaller palettes

Approximating coloring and maximum independent sets in 3-uniform hypergraphs

Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction

Computing optimal α-fat and α-small decompositions

Optimal planar point location

Polygonal path approximation with angle constraints

Reconstructing a collection of curves with corners and endpoints

Web caching using access statistics

Competitive on-line stream merging algorithms for media-on-demand

On-line restricted caching

Approximate majorization and fair online load balancing

Game theory, algorithms, and the Internet

Learning Markov networks: maximum bounded tree-width graphs

Approximately covering by cycles in planar graphs

Practical approximation algorithms for zero- and bounded-skew trees

Approximating the minimum strongly connected subgraph via a matching lower bound

Improved approximation algorithms for rectangle tiling and packing

Secure notarization of paper text documents

Sublinear time approximate clustering

Efficient oblivious transfer protocols

Constructing pseudo-random permutations with a prescribed structure

Robust algorithms for restricted domains

Polynomial algorithms for partitioning problems on graphs with fixed clique-width (extended abstract)

A polynomial time recognition algorithm for probe interval graphs

Colored Tutte polynomials and Kaufman brackets for graphs of bounded tree width

A new constructive root bound for algebraic expressions

Orderly spanning trees with applications to graph encoding and graph drawing

Alternatives to splay trees with O(log n) worst-case access times

Worst case constant time priority queue

Representing dynamic binary trees succinctly

Making data structures confluently persistent

Compact labeling schemes for ancestor queries

Better approximation algorithms for bin covering

New approaches to covering and packing problems

Parallel processor scheduling with delay constraints

Approximation algorithms for extensible bin packing

Scheduling precedence-constrained jobs with stochastic processing times on parallel machines

Loss-bounded analysis for differentiated services

Stability preserving transformations: packet routing networks with edge capacities and speeds

Distributed admission control, scheduling, and routing with stale information

On algorithms for efficient data migration

Fast distributed graph coloring with O(Δ) colors

Improved algorithms for fault tolerant facility location

Algorithms for facility location problems with outliers

The probabilistic relationship between the assignment and asymmetric traveling salesman problems

Approximation algorithms for data placement in arbitrary networks

Polynomial-time approximation schemes for geometric graphs

Morphing between polylines

Fast implementation of depth contours using topological sweep

Computing the depth of a flat

Which formulae shrink under random restrictions?

Selective families, superimposed codes, and broadcasting on unknown radio networks

Adversarial models in evolutionary game dynamics

The phase transition in 1-in-k SAT and NAE 3-SAT

Guessing secrets

Can entropy characterize performance of online algorithms?

Competitive auctions and digital goods

Towards understanding the predictability of stock markets from the perspective of computational complexity

Performance guarantee for online deadline scheduling in the presence of overload

Assigning chain-like tasks to a chain-like network

The inverse nearest neighbor problem with astrophysical applications

Reductions among high dimensional proximity problems

A cell probe lower bound for dynamic nearest-neighbor searching

Shape matching using edit-distance: an implementation

On validating planar worlds

Improved fast integer sorting in linear space

Single-source shortest-paths on arbitrary directed graphs in linear average-case time

Optimal constrained graph exploration

An efficient algorithm for the configuration problem of dominance graphs

Linear reductions of maximum matching

Internet packet filter management and rectangle geometry

Faster kinetic heaps and their use in broadcast scheduling

Finding least common ancestors in directed acyclic graphs

On binary searching with non-uniform costs

Soft kinetic data structures

Testing graphs for colorable properties

Random lifts of graphs

Improved results for route planning in stochastic transportation

Hill-climbing finds random planted bisections

On universally easy classes for NP-complete problems

The diameter of random massive graphs

Domatic partitions and the Lovász local lemma

Equitable colorings extend Chernoff-Hoeffding bounds

Universal configurations in light-flipping games

On the discrete Bak-Sneppen model of self-organized criticality

Can entropy characterize performance of online algorithms?

Content Provider	ACM Digital Library
Author	Pandurangan, Gopal Upfal, Eli
Abstract	We focus in this work on an aspect of online computation that is not addressed by the standard competitive analysis. Namely, identifying request sequences for which non-trivial online algorithms are useful versus request sequences for which all algorithms perform equally bad. The motivation for this work are advanced system and architecture designs which allow the operating system to dynamically allocate resources to online protocols such as prefetching and caching. To utilize these features the operating system needs to identify data streams that can benefit from more resources.Our approach in this work is based on the relation between entropy, compression and gambling, extensively studied in information theory. It has been shown that in some settings entropy can either fully or at least partially characterize the expected outcome of an iterative gambling game. Viewing online problem with stochastic input as an iterative gambling game, our goal is to study the extent to which the entropy of the input characterizes the expected performance of online algorithms for problems that arise in computer applications. We study bounds based on entropy for three online problems — list accessing, prefetching and caching. We show that entropy is a good performance characterizer for prefetching, but not so good characterizer for online caching.
Starting Page	727
Ending Page	734
Page Count	8
File Format	PDF
ISBN	0898714907
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2001-01-09
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in