The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
Culturally, computer scientists are generally trained in discrete mathematics; but continuous methods can give us surprising insights into many algorithms and combinatorial problems. In this pedagogical talk, I will describe two interesting places where continuous mathematics makes an entrance into computer science: proving lower bounds on the 3-colorability threshold in random graphs using differential...
We study the following geometric hypergraph coloring problem: given a planar point set and an integer k, we wish to color the points with k colors so that any axis-aligned strip containing sufficiently many points contains all colors. We show that if the strip contains at least 2k−1 points, such a coloring can always be found. In dimension d, we show that the same holds provided the strip contains...
The maximum empty rectangle problem is as follows: Given a set of red points in ℝd and an axis-aligned hyperrectangle B, find an axis-aligned hyperrectangle R of greatest volume that is contained in B and contains no red points. In addition to this problem, we also consider three natural variants: where we find a hypercube instead of a hyperrectangle, where we try to contain...
We prove a small linear-size kernel for the connected dominating set problem in planar graphs through data reduction. Our set of rules efficiently reduce a planar graph G with n vertices and connected dominating number γc(G) to a kernel of size at most 413γc(G) in O(n3) time answering the question of whether the connectivity...
We study the problem of designing truthful algorithms for scheduling a set of tasks, each one owned by a selfish agent, to a set of parallel (identical or unrelated) machines in order to minimize the makespan. We consider the following process: at first the agents declare the length of their tasks, then given these bids the protocol schedules the tasks on the machines. The aim of the protocol is to...
An O(n log2n) algorithm is presented to compute all coefficients of the chromatic polynomial of an n vertex graph of bounded tree-width. Previously, it has been known how to evaluate the chromatic polynomial for such graphs in linear time, implying a computation of all coefficients of the chromatic polynomial in quadratic time.
We propose an effective polynomial-time preprocessing strategy for intractable median problems. Developing a new methodological framework, we show that if the input instances of generally intractable problems exhibit a sufficiently high degree of similarity between each other on average, then there are efficient exact solving algorithms. In other words, we show that the median problems Swap Median...
Many divide-and-conquer algorithms employ the fact that the vertex set of a graph of bounded treewidth can be separated in two roughly balanced subsets by removing a small subset of vertices, referred to as a separator. In this paper we prove a trade-off between the size of the separator and the sharpness with which we can fix the size of the two sides of the partition. Our result appears to be a...
Consider a dark polygonal region in which intruders move freely, trying to avoid detection. A robot, which is equipped with a flashlight, moves along the polygon boundary to illuminate all intruders. We want to minimize the total distance traveled by the robot until all intruders are detected in the worst case. We present an O(nlogn) time and O(n) space algorithm for optimizing this metric, where...
Concurrent compositions of recursive programs with finite data are a natural abstraction model for concurrent programs. Since reachability is undecidable for this class, a restricted form of reachability has become popular in the formal verification literature, where the set of states reached within k context-switches, for a fixed small constant k, is explored. In this paper, we consider the language...
We consider the problem of minimizing the makespan on restricted related parallel machines. In restricted machine scheduling each job is only allowed to be scheduled on a subset of machines. We study the worst-case behavior of local search algorithms. In particular, we analyze the quality of local optima with respect to the jump, swap, push and lexicographical jump neighborhood.
The packet routing problem, i.e., the problem to send a given set of unit-size packets through a network on time, belongs to one of the most fundamental routing problems with important practical applications, e.g., in traffic routing, parallel computing, and the design of communication protocols. The problem involves critical routing and scheduling decisions. One has to determine a suitable (short)...
We investigate embeddings of graphs into the infinite extended grid graph. The problem was motivated by computation on adiabatic quantum computers, but it is related to a number of other well studied grid embedding problems. Such problems typically deal with representing vertices by grid points, and edges by grid paths, while minimizing some objective function such as the area or the maximum length...
We consider the multiplication of a sparse N ×N matrix A with a dense N ×N matrix B in the I/O model. We determine the worst-case non-uniform complexity of this task up to a constant factor for all meaningful choices of the parameters N (dimension of the matrices), k (average number of non-zero entries per column or row in A, i.e., there are in total kN non-zero entries), M (main memory size), and...
Over the recent years, a new linear method for compressing high-dimensional data (e.g., images) has been discovered. For any high-dimensional vector x, its sketch is equal to Ax, where A is an m×n matrix (possibly chosen at random). Although typically the sketch length m is much smaller than the number of dimensions n, the sketch contains enough information to recover an approximation to x. At the...
For a static array A of n totally ordered objects, a range minimum query asks for the position of the minimum between two specified array indices. We show how to preprocess A into a scheme of size 2n + o(n) bits that allows to answer range minimum queries on A in constant time. This space is asymptotically optimal in the important setting where access to A is not permitted after the preprocessing...
Binary relations are an important abstraction arising in a number of data representation problems. Each existing data structure specializes in the few basic operations required by one single application, and takes only limited advantage of the inherent redundancy of binary relations. We show how to support more general operations efficiently, while taking better advantage of some forms of redundancy...
We prove that the radix cross-section of a rational set for a length morphism, and more generally for a rational function from a free monoid into ℕ, is rational. This property no longer holds if the image of the function is a subset of a free monoid with two or more generators. The proof is based on several results on finite automata, such as the lexicographic selection of synchronous relations...
For each sufficiently large N, there exists a unary regular language L such that both L and its complement Lc are accepted by unambiguous nondeterministic automata with at most N states while the smallest deterministic automata for these two languages require a superpolynomial number of states, at least $e^{\Omega(\sqrt[3]{N\cdot\ln^{2}\!N})}\!$ . Actually, L and Lc are...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.