Titlebook: Automata, Languages, and Programming; 42nd International C Magnús M. Halldórsson,Kazuo Iwama,Bettina Speckman Conference proceedings 2015 S

PLUMP

Quantifying Competitiveness in Paging with Locality of Reference, of faults. Standard competitive analysis gives overly pessimistic results as it ignores the fact that real-world input sequences exhibit locality of reference. In this paper we study the paging problem using an intuitive and simple locality model that records inter-request distances in the input. A

escalate

Control-Group

几何学家

Batched Point Location in SINR Diagrams via Algebraic Tools,is heard at a specific location, in a setting consisting of . simultaneous transmitters and background noise. The SINR model gives rise to a natural geometric object, the ., which partitions the space into . regions where each of the transmitters can be heard and the remaining space where no transmi

小步走路

GROSS

油膏

Finding the Median (Obliviously) with Bounded Space,problem of determining whether the median is odd or even. It is nearly optimal since Chan, following Munro and Raman, has shown that there is a (randomized) selection algorithm using only . registers, each of which can store an input value or .-bit counter, that makes only . passes over the input. T

AGGER

BARGE

Solving Linear Programming with Constraints Unknown,onstraints is not necessary; the algorithm works as long as there exists an oracle that, on a proposed candidate solution, returns a violation in the form of a separating hyperplane. Can linear programming still be efficiently solved if the returned violation is in other formats?.Motivated by some r

确保