Startseite > Fachgruppen > Algorithmen und Komplexität > Lehre > Seminar: Gems of Theoretical Computer Science

# Seminar: Gems of Theoretical Computer Science

## Seminar, Winter Term 2018/19

The seminar based on a set of selected papers and textbook sections that demonstrate the beauty of problem solutions in the field of Theoretical Computer Science. We will find out that the preoccupation with sophisticated proof techniques, elegant arguments and surprising constructions is highly enjoyable. The seminar is inspired by the book "Perlen der Theoretischen Informatik " by Uwe Schöning, in which he presents a collection of results demonstrating highlights of Theoretical Computer Science. Of course, the selection of seminar topics is affected by the supervisor’s taste and research area. The seminar is expected to take place as a block seminar at the end of the lecture period.

Due to the high numbers of registered students, we have to start with a proposal phase: Each students that intends to take part in this seminar writes a proposal (1 page). Based on this proposal, we will select the participants of this year's seminar.

1. Describe your motivation for choosing this seminar. Mention courses in Theoretical Computer Science or related topics that you attended. Mention further experiences and qualifications that are useful for this seminar.
2. List three of the topics below (ordered by priority) that you find particularly interesting and give a short explanation why you find this topic interesting.

## Modul

• Seminar I / Seminar II

• Deadline of the proposal: October 4th, 2018.
Please send the proposal (1 page) as a PDF file by email to mafi@upb.de (Matthias Fischer). We recommend to use Latex.
• First meeting (distribution of topics):
October 9th, 2018, 4pm, Room F0.231, Fürstenallee 11
• Submission deadline of the seminar thesis (see Step II below):
December 17th, 2018
In order to get feedback, we strongly recommend to give a preliminary version to your advisor on December 1st.
• Submission deadline of the reviews (see Step III below):
January 14th, 2019
.
• Submission deadline of the final version of the seminar thesis:
January 28th, 2019
• Test presentations (see Step IV below):
January 21st - February 2nd, 2019
• Block Seminar, Presentation of your work (see Step I below):
February 4th and 5th, 2019

## Topics and Registrations

The topics are given in the first meeting. Reservations or defaults of issues are not possible. Your must register yourself in PAUL to attend this seminar. Unregistered students are not considered. The order of registration is of no importance. If there are more students interested in the seminar than places available, the selection of participants is made according to the study progress. For the seminar, e.g., the requirement would be the completed bachelor.

The seminar topics will be published here until the end of September. You should have a look at the topics and respective papers before the first meeting and make your mind up about your topic preferences.

I) Presentation

II) Seminar thesis

• Essay of length 12 to 20 pages written according to the standards of a scientific paper
• details see below

III) Reviews

• Peer review procedure similar to scientific publications
• You submit your thesis (paper) at easychair.org
• Some (2) peers (other students) review your submission
• Read and understand the submitted paper
• Make recommendations on how to improve
• The reviews you receive will not influence (but your final version)
• Each student has to write 2 reviews (each 1-2 pages)

IV) Test run of your presentation

• Do a test run with your presentation.
• Meet in groups of approx. 3-4 students
• Give each other feedback
• Negotiate date yourselves
• Tell us when and where you plan to meet (mandatory!)
• We can organize a room for you if necessary

We expect your active participation (as opposed to mere attendance) at all presentations of this seminar.

We will grade the quality of the presentation and the quality of the essay / seminar thesis individually. You have to pass (i.e., 4.0 or better) each part individually to pass this course. Note that commitment, diligence, and compliance with our deadlines will be taken into account.

## Remarks

General

Each topic has one or several references that should be understood as starting points for your research. Hence, it is very likely that you will need further papers or textbooks to fully understand your topic. The actual content of your seminar thesis as well as your seminar talk should be discussed with your adviser.
It is your responsibility to contact your adviser and schedule appointments with them early enough. We strongly recommend you to discuss questions regarding the topic, the composition, and the structure of your written seminar thesis with your adviser. The same holds for your seminar talk. Note that finding an appointment directly before your thesis' submission or seminar talk cannot be guaranteed, since the advisers need to arrange their appointments with their own teaching and research.

Seminar Thesis

We expect an essay of length 12 to 20 pages written according to the standards of a scientific paper. A simple summary of the referenced literature is insufficient. We expect you to identify the important ideas and proofs of the referenced literature and present them in a correct and appropriate way. The mandatory typesetting for your thesis is LaTeX (see below for details). All citations must be marked as such and referenced with their origin. Plagiarism directly leads to failure of the seminar. Note that plagiarism not only includes copies from the original literature, but also copies from other authors (e.g., other seminar theses) or translations of them.

Title and Abstract

Create a brief abstract that summarizes the problem and the main results. An abstract is kept short (typically 10-20 lines). Also make up a title for your thesis (note that this is not necessarily the title of the used literature or the title from our topic list). It is important to make your own reasoning about a title that describes the thesis best from your point of view.

References

Each thesis contains a reference list that contains at least the literature used in your thesis. In the digital libraries of DBLP, ACM, IEEE, or Springer you can find detailed literature reference information. For conferencing proceedings or journals ALWAYS specify the pages. For journals, additionally provide volume and journal number. Do not rely on the authors to do their references correct (e.g., reference list in a paper or at the author's website). Sometimes this references are wrong are incomplete. Also do not rely on search engines like CiteSeer or Google Scholar: always verify the correctness and completeness of your references. Especially, it is insufficient if you only provide links to the papers or citations in the web.

# Topics

## (1) Finding Large Sticks and Potatoes in Polygons

This paper studies a class of optimization problems in polygons that seek to compute the "largest" subset of a prescribed type, e.g., a longest line segment ("stick") or a maximum-area triangle or convex body ("potato"). Exact polynomial-time algorithms are known for some of these problems, but their time bounds are high (e.g., O(n^7) for the largest convex polygon in a simple n-gon). They devise efficient approximation algorithms for these problems. In particular, they give near-linear time algorithms for a (1-ε)-approximation of the biggest stick, an O(1)-approximation of the maximum-area convex body, and a (1-ε)-approximation of the maximum-area fat triangle or rectangle. In addition, they give efficient methods for computing large ellipses inside a polygon (whose vertices are a dense sampling of a closed smooth curve). The algorithms include both deterministic and randomized methods, one of which has been implemented (for computing large area ellipses in a well sampled closed smooth curve).

## (2) Direct Visibility of Point Sets

This paper proposes a simple and fast operator, the "Hidden" Point Removal operator, which determines the visible points in a point cloud, as viewed from a given viewpoint. Visibility is determined without reconstructing a surface or estimating normals. It is shown that extracting the points that reside on the convex hull of a transformed point cloud, amounts to determining the visible points. This operator is general - it can be applied to point clouds at various dimensions, on both sparse and dense point clouds, and on viewpoints internal as well as external to the cloud. It is demonstrated that the operator is useful in visualizing point clouds, in view-dependent reconstruction and in shadow casting.

## (3) Online Facility Location against a t-bounded adversary

The paper explores the classical Online Facility Location problem, in which clients appear one at a time in a given metric space, and which must be served by connecting them to an open facility. Each facility which is opened by the algorithm is associated with a given cost. The goal is to minimize the overall costs composed of the costs for facilities and the cost of connecting clients, where the cost equals the distance to the next facility.
Instead of a worst case sequence, which is shown to produce large approximation factors, the author considers bounded adversaries, which can select the positions of the clients, but the order of arrival of those clients can only be partially influenced. The result is an order somewhere between a worst case ordering and a purely random one. It is proven that the worst case approximation smoothly improves as the randomness in the ordering increases.

Conference Paper: https://doi.org/10.1137/1.9781611975031.65

Full Version:  https://arxiv.org/abs/1711.09384

## (4) The (h, k)-server problem on bounded depth trees

The authors consider an augmentation of the classical k-Server Problem: Given are k servers located in some metric space. In each round, one requests arrives and needs to be served by moving one of the serves to the point of the request. The goal is to minimize the total movement.
While this problem is well explored for the case where the performance of an online algorithm (the requests arrive one-by-one and must be served instantly) is compared to the optimal solution (which knows all requests in advance) with the same number of servers (h=k), the problem of determining the ratio for an optimal solution which uses strictly less than k servers (h<k) is still open for most metrics. This papers shows a ratio independent of h and k for bounded depth trees.

Conference Paper: http://dl.acm.org/citation.cfm?id=3039686.3039751

Full Version: https://arxiv.org/abs/1608.08527

## (5) Deterministic Decremental Single Source Shortest Paths : Beyond the O (mn) Bound

In this paper we consider the decremental single-source shortest paths (SSSP) problem, where given a graph G and a source node s the goal is to maintain shortest paths between s and all other nodes in G under a sequence of online adversarial edge deletions. In their seminal work, Even and Shiloach [JACM 1981] presented an exact solution to the problem with only O(mn) total update time over all edge deletions. Their classic algorithm was the best known result for the decremental SSSP problem for three decades, even when approximate shortest paths are allowed. In fact, all known improvements over the Even-Shiloach algorithm are randomized. All these algorithms maintain some truncated shortest path trees from a small subset of nodes. While in the randomized setting it is possible to “hide” these nodes from the adversary, in the deterministic setting this is impossible: the adversary can delete all edges touching these nodes, thus forcing the algorithm to choose a new set of nodes and incur a new computation of shortest paths. In this paper we present the first deterministic decremental SSSP algorithm that breaks the Even-Shiloach bound of O(mn) total update time, for unweighted and undirected graphs. Our algorithm is (1 + ) approximate and achieves a total update time of Õ(n2 ). Our algorithm can also achieve the same bounds in the incremental setting. It is worth mentioning that for dense instances where m = Ω(n2−1/ log(n) ), our algorithm is also faster than all existing randomized algorithms.

## (6) Deterministic and Probabilistic Binary Search in Graphs

We consider the following natural generalization of Binary Search: in a given undirected, positively weighted graph, one vertex is a target. The algorithm’s task is to identify the target by adaptively querying vertices. In response to querying a node q, the algorithm learns either that q is the target, or is given an edge out of q that lies on a shortest path from q to the target. We study this problem in a gen- eral noisy model in which each query independently receives a correct answer with probability p > 12 (a known constant), and an (adversarial) incorrect one with probability 1 − p. Our main positive result is that when p = 1 (i.e., all answers are correct), log2 n queries are always sufficient. For general p, we give an (almost information-theoretically optimal) algorithm that uses, in expectation, no more than (1−δ) log n  +o(log n)+O(log2 (1/δ)) queries, and identifies 1−H(p) the target correctly with probability at least 1 − δ. Here, H(p) = −(p log p + (1 − p) log(1 − p)) denotes the entropy. The first bound is achieved by the algorithm that iteratively queries a 1-median of the nodes not ruled out yet; the second bound by careful repeated invocations of a multiplicative weights algorithm. Even for p = 1, we show several hardness results for the problem of determining whether a target can be found using K queries. Our upper bound of log2 n implies a quasipolynomial-time algorithm for undirected connected graphs; we show that this is best-possible under the Strong Exponential Time Hypothesis (SETH). Furthermore, for di- rected graphs, or for undirected graphs with non-uniform node querying costs, the problem is PSPACE-complete. For a semi-adaptive version, in which one may query r nodes each in k rounds, we show membership in Σ2k−1 in the polynomial hierarchy, and hardness for Σ2k−5.

## (7) Autonomous mobile robots with lights

We consider the well known distributed setting of computational mobile entities, called robots, operating in the Euclidean plane in Look-Compute-Move (LCM) cycles. We investigate the computational impact of expanding the capabilities of the robots by endowing them with an externally visible memory register, called light, whose values, called colors, are persistent, that is they are not automatically reset at the end of each cycle. We refer to so endowed entities as luminous robots. We study the computational power of luminous robots with respect to the three main settings of activation and synchronization: fully-synchronous, semi-synchronous, and asynchronous. We establish several results. A main contribution is the constructive proof that asynchronous robots, illuminated with a constant number of colors, are strictly more powerful than traditional semi-synchronous robots. We also constructively prove that, for luminous robots, the difference between asynchrony and semi-synchrony disappears. This result must be contrasted with the strict dominance between the models without lights (even if the robots are enhanced with an unbounded amount of persistent internal memory). Additionally we show that there are problems that robots cannot solve without lights, even if they are fully-synchronous, but can be solved by asynchronous luminous robots with O (1) colors. It is still open whether or not asynchronous luminous robots with O (1) colors are more powerful than fully-synchronous robots without lights. We prove that this is indeed the case if the robots have the additional capability of remembering a single snapshot. This in turn shows that, for asynchronous robots, to have O(1) colors and a single snapshot renders them more powerful than to have an unlimited amount of persistent memory (including snapshots) but no lights.

## (8) Meeting in a Polygon by Anonymous Oblivious Robots

The Meeting problem for k ≥ 2 searchers in a polygon P (possibly with holes) consists in making the searchers move within P, according to a distributed algorithm, in such a way that at least two of them eventually come to see each other, regardless of their initial positions. The polygon is initially unknown to the searchers, and its edges obstruct both movement and vision. Depending on the shape of P, we minimize the number of searchers k for which the Meeting problem is solvable. Specifically, if P has a rotational symmetry of order σ (where σ = 1 corresponds to no rotational symmetry), we prove that k = σ + 1 searchers are sufficient, and the bound is tight. Furthermore, we give an improved algorithm that optimally solves the Meeting problem with k = 2 searchers in all polygons whose barycenter is not in a hole (which includes the polygons with no holes). Our algorithms can be implemented in a variety of standard models of mobile robots operating in Look-Compute-Move cycles. For instance, if the searchers have memory but are anonymous, asynchronous, and have no agreement on a coordinate system or a notion of clockwise direction, then our algorithms work even if the initial memory contents of the searchers are arbitrary and possibly misleading. Moreover, oblivious searchers can execute our algorithms as well, encoding information by carefully positioning themselves within the polygon. This code is computable with basic arithmetic operations (provided that the coordinates of the polygon’s vertices are algebraic real numbers in some global coordinate system), and each searcher can geometrically construct its own destination point at each cycle using only a compass. We stress that such memoryless searchers may be located anywhere in the polygon when the execution begins, and hence the information they initially encode is arbitrary. Our algorithms use a self- stabilizing map construction subroutine which is of independent interest.

## (9) Online Lower Bounds via Duality (Azar et al. SODA 2017)

In this paper, we exploit linear programming duality in the online setting, where input arrives on the ﬂy, from the unique perspective of designing lower bounds (i.e., hardness results) on the competitive ratio. In particular, we provide a systematic method (as opposed to ad hoc case analysis that is typically done) for obtaining online deterministic and randomized lower bounds on the competitive ratio for a wide variety of problems. We show the usefulness of our approach by providing new, tight hardness results for three diverse online problems: the Vector Bin Packing problem, Ad-auctions (and various online matching problems), and the Capital Investment problem. Our methods are suﬃciently general that they can also be used to reconstruct existing lower bounds. Our approach is in stark contrast to previous works, which exploit linear programming duality to obtain positive results, often via the useful primaldual scheme. We design a general recipe with the opposite aim of obtaining negative results via duality. The general idea behind our approach is to construct a parameterized family of primal linear programs based on a candidate collection of input sequences for proving the lower bound, where the objective function corresponds to optimizing the competitive ratio. Solving the parameterized family of primal linear programs optimally would yield a valid lower bound, but is a challenging task and limits the tools that can be applied, since analysis must be done precisely and exact optimality needs to be proved. To this end, we consider the corresponding parameterized family of dual linear programs and provide feasible solutions, where the objective function yields a lower bound on the competitive ratio. This opens up additional doors for analysis, including some of the techniques we employ (e.g., continuous analysis, diﬀerential equations, etc.), as we need not be so careful about exact optimality. We are conﬁdent that our methods can be successfully applied to produce many more lower bounds for a wide array of online problems.

## (10) Online Service with Delay (Azar et al. STOC 2017)

In this paper, we introduce the online service with delay problem. In this problem, there are n points in a metric space that issue service requests over time, and a server that serves these requests. The goal is to minimize the sum of distance traveled by the server and the total delay (or a penalty function thereof) in serving the requests. This problem models the fundamental tradeoff between batching requests to improve locality and reducing delay to improve response time, that has many applications in operations management, operating systems, logistics, supply chain management, and scheduling.
Our main result is to show a poly-logarithmic competitive ratio for the online service with delay problem. This result is obtained by an algorithm that we call the preemptive service algorithm. The salient feature of this algorithm is a process called preemptive service, which uses a novel combination of (recursive) time forwarding and spatial exploration on a metric space. We also generalize our results to k > 1 servers, and obtain stronger results for special metrics such as uniform and star metrics that correspond to (weighted) paging problems.

## (11) An Improved Scheduling-Algorithm for Machine Minimization

In their paper [1], Chuzhoy et al. study a scheduling problem in which $n$ jobs characterized by release times, deadlines and arbitrary sizes need to be scheduled on a minimum number of machines such that all deadlines are met. They propose a polynomial-time algorithm which provides $O(\sqrt{\log n/ \log \log n})$-approximations and which is based on (randomized) rounding of an optimal (fractional) solution to a suitable linear program. It improves upon the previously best known $O(\log n/ \log \log n)$-approximation algorithm dated back to 1987 [2].

[1] J. Chuzhoy, S. Guha, S. Khanna, and J. Naor. Machine Minimization for Scheduling Jobs with Interval Constraints. In Proceedings of the 45th Symposium on Foundations of Computer Science, pp. 81-90, 2004.

[2] P. Raghavan and C.D. Thompson. Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica, 7(4):365-374, 1987

## (12) Approximation Schemes for Scheduling on Uniformly Related Parallel Machines

In their paper [1], Epstein and Sgall give a polynomial approximation scheme for the problem of scheduling on uniformly related
parallel machines for a large class of objective functions that depend only on the machine completion times.
Examples of such objective functions are minimizing the maximal completion time (makespan) or maximizing the minimum load of any machine.
The paper generalizes and unifies previous results in this area.

[1] L. Epstein, and J. Sgall. Approximation schemes for scheduling on uniformly related and identical parallel machines. Algorithmica, 39(1):43-57, 2004

## (13) Fully Dynamic MIS in Uniformly Sparse Graphs

In the Maximal Independent Set (MIS) Problem, we search for a set of nodes such that no two nodes are connected by an edge. The set should be maximal, i.e., adding any node to the set will violate the stated property. In this paper, the authors show how to efficiently maintain such a set in a graph which is subject to edge insertions and deletions. The underlying graph is assumed to be sparse, i.e., it has low edge density.

Conference Paper: https://doi.org/10.4230/LIPIcs.ICALP.2018.92

Full Version: https://arxiv.org/abs/1808.10316

## (14) Distributed computing by mobile robots: uniform circle formation

Consider a set of n finite set of simple autonomous mobile robots (asynchronous, no common coordinate system, no identities, no central coordination, no direct communication, no memory of the past, non-rigid, deterministic) initially in distinct locations, moving freely in the plane and able to sense the positions of the other robots. We study the primitive task of the robots arranging themselves on the vertices of a regular n-gon not fixed in advance (Uniform Circle Formation). In the literature, the existing algorithmic contributions are limited to conveniently restricted sets of initial configurations of the robots and to more powerful robots. The question of whether such simple robots could deterministically form a uniform circle has remained open. In this paper, we constructively prove that indeed the Uniform Circle Formation problem is solvable for any initial configuration in which the robots are in distinct locations, without any additional assumption (if two robots are in the same location, the problem is easily seen to be unsolvable). In addition to closing a long-standing problem, the result of this paper also implies that, for pattern formation, asynchrony is not a computational handicap, and that additional powers such as chirality and rigidity are computationally irrelevant.

## (15) Strong LP formulations for scheduling splittable jobs on unrelated machines

A natural extension of the makespan minimization problem on unrelated machines is to allow jobs to be partially processed by different machines while incurring an arbitrary setup time. In [1], the authors present increasingly stronger LP-relaxations for this problem and their implications on the approximability of the problem. They show that the straightforward LP, extending the approach for the original problem, has an integrality gap of 3 and yields an approximation algorithm of the same factor. By applying a lift-and-project procedure, the authors are able to improve both the integrality gap and the implied approximation factor to 1+ϕ, where ϕ is the golden ratio. They also show that the problem cannot be approximated within a factor better than e/e11.582 (unless P=NP), which is larger than the inapproximability bound of 1.5 for the original problem.

[1] Correa, J., Marchetti-Spaccamela, A., Matuschke, J., Stougie, L., Svensson, O., Verdugo, V., & Verschae, J. (2015). Strong LP formulations for scheduling splittable jobs on unrelated machines. Mathematical Programming, 154(1-2), 305-328.

# Submission of your Seminar Thesis

The thesis has to be created with LaTeX using our customized version of Springer's svmult-Style package for Springer's manuscript guidelines of Contributed Books (with changes as explained below). We will create a complete volume consisting of all submissions.

You have to submit the LaTeX sources AND a complete pdf of your seminar thesis by mail. The mail shall contain only one zip or tar.gz file with these data and must be sent to Matthias Fischer. Please do NOT include your matriculation number in your thesis.

For the LaTeX document you have to follow the following rules of the game:

• The document must be compiled with pdflatex. Hence, pictures must to be included as pdf, jpg or png.
• There is only one "*.tex" file for your complete seminar thesis.
• For an easy start: use the file "author.tex" from the svmult-package and extend it. All pictures and the LaTeX file itself have to be contained in the same directory.
• Your file must be encoded in UTF-8.
• Your highest breakdown-level is \section. (Thus, you can use \section, \subsection, \subsubsection, \paragraph, etc.)
• To distinguish all self-defined commands, labels and references, each author gets his own prefix. (Example: the author "Matthias Fischer" gets his unique prefix "MaFi".)
• Each command, label and reference consists of the prefix, followed by an individual identifier. Thus, if Matthias wants to call a label "myCoolLabel", the label has to be defined by \label{MaFiMyCoolLabel}.
• The name of your LaTeX file consists only of your prefix supplemented by the suffix ".tex" (e.g., "MaFi.tex"). Each picture is prefixed with your personal prefix.
• We only use the svmult theorem environment. This means, the option "nospthms" and the package "amsthm" can not be used. (The package "amsthm" is not compatible to "svmult".)
• We do not use the BibTeX compiler to process literature references. Instead of this, you have to add your literature references like presented in the svmult template file "reference.tex". However, you do not use two files but include the references at the end of your thesis file. You have to follow the style given in the template file, i.e., "author, year, title,...".
• To format the pseudocode of your algorithms you can either use "algorithmicx" together with its floating environment "algorithm" from the package "algorithms", or you can use the "listings" environment. We recommend to start with predefined commands as given by package "algpseudocode". We do not use the package "algorithmic".
\documentclass{svmult}
\usepackage[utf8x]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{makeidx}
\usepackage{graphicx}
\usepackage{multicol}
\usepackage[bottom]{footmisc}
\usepackage{amsmath, amssymb, amsfonts, amscd}
\usepackage{algpseudocode}
\usepackage{algorithm}
\usepackage{listings}
\usepackage{verbatim}
\makeindex
• Further packages are not allowed. The page size as defined by svmult is too small for our purposes: Use the following customized svmult file to replace the file shipped with the Springer package: use this file!