NDLI: Tight lower bounds for the online labeling problem

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

Faster approximate multicommodity flow using quadratically coupled flows

Quantum money from hidden subspaces

The cell probe complexity of dynamic range counting

Polyhedral clinching auctions and the adwords polytope

Computing a nonnegative matrix factorization -- provably

Short proofs for the determinant identities

Solution of the propeller conjecture in $R^{3}$

From irreducible representations to locally decodable codes

Approximation algorithms for semi-random partitioning problems

Prior-free auctions with ordered bidders

Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates

Fast matrix rank algorithms and applications

Jacobian hits circuits: hitting-sets, lower bounds for depth-D occur-k formulas & depth-3 transcendence degree-k circuits

The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme

Learning poisson binomial distributions

Competitive contagion in networks

Pseudorandom generators with long stretch and low locality from random local one-way functions

Routing in undirected graphs with constant congestion

Catching the k-NAESAT threshold

Tight bounds for distributed functional monitoring

A complementary pivot algorithm for markets under separable, piecewise-linear concave utilities

Monotone expansion

Multi-way spectral partitioning and higher-order cheeger inequalities

On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption

When the cut condition is enough: a complete characterization for multiflow problems in series-parallel networks

Certifiable quantum dice: or, true random number generation secure against quantum adversaries

Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds

Matroid prophet inequalities

On identity testing of tensors, low-rank recovery and compressed sensing

Time-space tradeoffs in resolution: superpolynomial lower bounds for superlinear space

2log1-ε n hardness for the closest vector problem with preprocessing

Folded codes from function field towers and improved optimal rate list decoding

A near-linear time ε-approximation algorithm for geometric bipartite matching

On the limits of black-box reductions in mechanism design

Tight bounds for monotone switching networks via fourier analysis

Nearly optimal sparse fourier transform

Separating multilinear branching programs and formulas

On vertex sparsifiers with Steiner nodes

Nearly optimal solutions for the chow parameters problem and low-weight approximation of halfspaces

Finding red balloons with split contracts: robustness to individuals' selfishness

Characterizing pseudoentropy and simplifying pseudorandom generator constructions

Improving christofides' algorithm for the s-t path TSP

Complexity of counting CSP with complex weights

Global computation in a poorly connected world: fast rumor spreading with no dependence on conductance

Rational proofs

Nearly complete graphs decomposable into large induced matchings and their applications

Many sparse cuts via higher eigenvalues

Multiparty computation secure against continual memory leakage

Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives

Span programs for functions with constant-sized 1-certificates: extended abstract

Online matching with concave returns

Structure theorem and isomorphism test for graphs with excluded topological subgraphs

On the virtue of succinct proofs: amplifying communication complexity hardness to time-space trade-offs in proof complexity

A new point of NP-hardness for unique games

Subspace evasive sets

Using petal-decompositions to build a low stretch spanning tree

Budget feasible mechanism design: from prior-free to bayesian

Interactive information complexity

Polynomial time algorithms for multi-type branching processesand stochastic context-free grammars

Reconstruction of depth-4 multilinear circuits with top fan-in 2

Approximation algorithms and hardness of integral concurrent flow

Making polynomials robust to noise

An analysis of one-dimensional schelling segregation

Design extractors, non-malleable condensers and privacy amplification

Multiplying matrices faster than coppersmith-winograd

The freezing threshold for k-colourings of a random graph

Tight time-space tradeoff for mutual exclusion

Minimax option pricing meets black-scholes in the limit

Probabilistic existence of rigid combinatorial structures

Approximating the exponential, the lanczos method and an Õ(m)-time spectral algorithm for balanced separator

Beating randomized response on incoherent matrices

Determinism versus nondeterminism with arithmetic tests and computation: extended abstract

Hypercontractivity, sum-of-squares proofs, and their applications

Edge transitive ramanujan graphs and symmetric LDPC good codes

Improved smoothed analysis of multiobjective optimization

An algorithmic characterization of multi-dimensional mechanisms

The multiparty communication complexity of set disjointness

Optimal online buffer scheduling for block devices

Affine projections of polynomials: extended abstract

Robust satisfiability of constraint satisfaction problems

A tight RMR lower bound for randomized mutual exclusion

A quantitative gibbard-satterthwaite theorem without neutrality

From query complexity to computational complexity

Matroids and integrality gaps for hypergraphic steiner tree relaxations

Unconditional differentially private mechanisms for linear queries

Strict fibonacci heaps

Optimal private halfspace counting via discrepancy

Tight lower bounds for the online labeling problem

Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels

Tight lower bounds for the online labeling problem

Content Provider	ACM Digital Library
Author	Bulánek, Jan Saks, Michael Koucký, Michal
Abstract	We consider the file maintenance problem (also called the online labeling problem) in which n integer items from the set {1,.,r} are to be stored in an array of size m ≥ n. The items are presented sequentially in an arbitrary order, and must be stored in the array in sorted order (but not necessarily in consecutive locations in the array). Each new item must be stored in the array before the next item is received. If r ≤ m then we can simply store item j in location j but if r>m then we may have to shift the location of stored items to make space for a newly arrived item. The algorithm is charged each time an item is stored in the array, or moved to a new location. The goal is to minimize the total number of such moves the algorithm has to do. This problem is non-trivial when n ≤ m < r. In the case that m = Cn for some C>1, algorithms for this problem with cost $O(log(n)^{2})$ per item have been given [Itai et al. (1981), Willard (1992), Bender et al. (2002)]. When m=n, algorithms with cost $O(log(n)^{3})$ per item were given [Zhang (1993),Bird and Sadnicki (2007)]. In this paper we prove lower bounds that show that these algorithms are optimal, up to constant factors. Previously, the only lower bound known for this range of parameters was a lower bound of $Ω(log(n)^{2})$ for the restricted class of smooth algorithms [Dietz et al. (2005), Zhang (1993)]. We also provide an algorithm for the sparse case: If the number of items is polylogarithmic in the array size then the problem can be solved in amortized constant time per item.
Starting Page	1185
Ending Page	1198
Page Count	14
File Format	PDF MP4
ISBN	9781450312455
DOI	10.1145/2213977.2214083
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2012-05-19
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Lower bounds Online labeling File maintenance problem
Content Type	Audio 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