Mini Workshop on Online and Distributed Aspects
of Decision Making
Monday, December 14 2020, via zoom
Organizer: Spyros Angelopoulos (CNRS and Sorbonne University)
Organizer: Spyros Angelopoulos (CNRS and Sorbonne University)
https://zoom.us/j/95018364510?pwd=UXVWSEdXYmNidWlSaFN0U1EyVWZ4UT09
Meeting ID: 950 1836 4510
Passcode: Vh7T3m
9:00 -- 9:45 Nikhil Bansal (TU Eindhoven)
Title: Myopic Weighted Paging
Abstract: Inspired by Belady's optimal algorithm for unweighted paging, we consider a natural myopic model for weighted paging in which an algorithm has access to the relative ordering of all pages with respect to the time of their next arrival. The problem turns out to have interesting connections to certain geometric allocation problems, that have been previously studied in the context of the k-server problem. We will describe tight deterministic and randomized bounds for these problems, and explain the conceptual new difficulties underlying these problems and the new ideas needed besides the standard multiplicative update based approaches.
9:45--10:15 Pierre Fraigniaud (CNRS and University of Paris -- IRIF)
Title: Distributed Interactive Proofs
Abstract : This talk will introduce the audience with the notion of interactive proofs in the distributed setting, as defined by Kol, Oshman and Saxena (2018). In particular, the talk will present the general compiler by Naor, Parter, and Yogev (2020) enabling to convert centralized interactive proofs to protocols where the verifier is distributed, and will discuss the performances of this compiler for specific decision problems, including graph planarity.
10:15 -- 10:30 Break
10:30-11:00 Christoph Dürr (CNRS and Sorbonne University -- LIP6)
Title: Scheduling with a processing time oracle
Abstract: In this talk we study a single machine scheduling problem with the objective of minimizing the sum of completion times. Each of the given jobs is either short or long. This information is necessary to produce the optimal schedule. However it is initially hidden to the algorithm, only the execution of a processing time oracle reveals the processing time of a given job. These tests occupy time on the schedule, therefore the algorithm must decide for which jobs it will call the processing time oracle. The objective value of the resulting schedule is compared with the objective value of an optimal schedule, which is computed using full information. The resulting competitive ratio measures the price of hidden processing times.
Two models are studied. In the non-adaptive model, the algorithm needs to decide before hand which jobs to test, and which jobs to execute untested. However in the adaptive model, the algorithm can make these decisions adaptively to the outcomes of the job tests. In both models we provide optimal polynomial time two-phase algorithms, which consist of a first phase where jobs are tested, and a second phase where jobs are executed obliviously. Experiments give strong evidence that optimal algorithms have this structure. Proving this property is left as an open problem.
Joint work with Fanny Dufossé, Noël Nadal, Denis Trystram, Óscar C. Vásquez (arXiv:2005.03394)
11:00-- 11:30 Spyros Angelopoulos (CNRS and Sorbonne University -- LIP6)
Title: Online Search With a Hint
Abstract: The linear search problem, informally known as the cow path problem, is one of the fundamental problems in search theory. In this problem, an immobile target is hidden at some unknown position on an unbounded line, and a mobile searcher, initially positioned at some specific point of the line called the root, must traverse the line so as to locate the target. The objective is to minimize the worst-case ratio of the distance traversed by the searcher to the distance of the target from the root, which is known as the competitive ratio of the search.
In this work we study this problem in a setting in which the searcher has a hint concerning the target. We consider three settings in regards to the nature of the hint: i) the hint suggests the exact position of the target on the line; ii) the hint suggests the direction of the optimal search (i.e., to the left or the right of the root); and iii) the hint is a general k-bit string that encodes some information concerning the target. Our objective is to study the Pareto-efficiency of strategies in this model. Namely, we seek optimal, or near-optimal tradeoffs between the searcher's performance if the hint is correct (i.e., provided by a trusted source) and if the hint is incorrect (i.e., provided by an adversary).
11:30--12:00 Steve Alpern (Warwick Business School)
Title: The Faulty GPS Problem: Shortest Time Paths in Networks with Unreliable Directions
Abstract: At every branch node of a network Q, a Satnav (GPS) points to the arc leading to the destination, or home node, H - but only with a high known probability p. Always trusting the Satnav's suggestion may lead to an infinite cycle. If one wishes to reach H in least expected time, with what probability q=q(Q,p) should one trust the pointer (if not, one chooses randomly among the other arcs)? We call this the Faulty Satnav (GPS) Problem. We also consider versions where the trust probability q can depend on the degree of the current node and a `treasure hunt' where two searchers try to reach H first.
This problem has its origin not in driver frustration but in the work of Fonio et al (2017) on ant navigation, where the pointers correspond to pheromone markers pointing to the nest.