Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAn $Omega(log n)$ Lower Bound for Online Matching on the Line
69
0
0.0
(
0
)
Added by
Kangning Wang
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Authors
Kangning Wang
Ask ChatGPT about the research
No Arabic abstract
For online matching with the line metric, we present a lower bound of $Omega(log n)$ on the approximation ratio of any online (possibly randomized) algorithm. This beats the previous best lower bound of $Omega(sqrt{log n})$ and matches the known upper bound of $O(log n)$.
rate research
Read More
Given two strings $S$ and $P$, the Episode Matching problem is to compute the length of the shortest substring of $S$ that contains $P$ as a subsequence. The best known upper bound for this problem is $tilde O(nm)$ by Das et al. (1997), where $n,m$ are the lengths of $S$ and $P$, respectively. Although the problem is well studied and has many applications in data mining, this bound has never been improved. In this paper we show why this is the case by proving that an $O((nm)^{1-epsilon})$ algorithm (even for binary strings) would refute the popular Strong Exponential Time Hypothesis (SETH). The proof is based on a simple reduction from Orthogonal Vectors.
In this paper, we show a connection between a certain online low-congestion routing problem and an online prediction of graph labeling. More specifically, we prove that if there exists a routing scheme that guarantees a congestion of $alpha$ on any edge, there exists an online prediction algorithm with mistake bound $alpha$ times the cut size, which is the size of the cut induced by the label partitioning of graph vertices. With previous known bound of $O(log n)$ for $alpha$ for the routing problem on trees with $n$ vertices, we obtain an improved prediction algorithm for graphs with high effective resistance. In contrast to previous approaches that move the graph problem into problems in vector space using graph Laplacian and rely on the analysis of the perceptron algorithm, our proof are purely combinatorial. Further more, our approach directly generalizes to the case where labels are not binary.
We study an online hypergraph matching problem with delays, motivated by ridesharing applications. In this model, users enter a marketplace sequentially, and are willing to wait up to $d$ timesteps to be matched, after which they will leave the system in favor of an outside option. A platform can match groups of up to $k$ users together, indicating that they will share a ride. Each group of users yields a match value depending on how compatible they are with one another. As an example, in ridesharing, $k$ is the capacity of the service vehicles, and $d$ is the amount of time a user is willing to wait for a driver to be matched to them. We present results for both the utility maximization and cost minimization variants of the problem. In the utility maximization setting, the optimal competitive ratio is $frac{1}{d}$ whenever $k geq 3$, and is achievable in polynomial-time for any fixed $k$. In the cost minimization variation, when $k = 2$, the optimal competitive ratio for deterministic algorithms is $frac{3}{2}$ and is achieved by a polynomial-time thresholding algorithm. When $k>2$, we show that a polynomial-time randomized batching algorithm is $(2 - frac{1}{d}) log k$-competitive, and it is NP-hard to achieve a competitive ratio better than $log k - O (log log k)$.
This paper considers the online machine minimization problem, a basic real time scheduling problem. The setting for this problem consists of n jobs that arrive over time, where each job has a deadline by which it must be completed. The goal is to design an online scheduler that feasibly schedules the jobs on a nearly minimal number of machines. An algorithm is c-machine optimal if the algorithm will feasibly schedule a collection of jobs on cm machines if there exists a feasible schedule on m machines. For over two decades the best known result was a O(log P)-machine optimal algorithm, where P is the ratio of the maximum to minimum job size. In a recent breakthrough, a O(log m)-machine optimal algorithm was given. In this paper, we exponentially improve on this recent result by giving a O(log log m)-machine optimal algorithm.
We prove a lower bound on the space complexity of two-pass semi-streaming algorithms that approximate the maximum matching problem. The lower bound is parameterized by the density of Ruzsa-Szemeredi graphs: * Any two-pass semi-streaming algorithm for maximum matching has approximation ratio at least $(1- Omega(frac{log{RS(n)}}{log{n}}))$, where $RS(n)$ denotes the maximum number of induced matchings of size $Theta(n)$ in any $n$-vertex graph, i.e., the largest density of a Ruzsa-Szemeredi graph. Currently, it is known that $n^{Omega(1/!loglog{n})} leq RS(n) leq frac{n}{2^{O(log^*{!(n)})}}$ and closing this (large) gap between upper and lower bounds has remained a notoriously difficult problem in combinatorics. Under the plausible hypothesis that $RS(n) = n^{Omega(1)}$, our lower bound is the first to rule out small-constant approximation two-pass semi-streaming algorithms for the maximum matching problem, making progress on a longstanding open question in the graph streaming literature.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
