Zobrazeno 1 - 10
of 289
pro vyhledávání: '"Pruhs, Kirk"'
Datalogo is an extension of Datalog that allows for aggregation and recursion over an arbitrary commutative semiring. Like Datalog, Datalogo programs can be evaluated via the natural iterative algorithm until a fixed point is reached. However unlike
Externí odkaz:
http://arxiv.org/abs/2312.14063
Motivated by demand-responsive parking pricing systems, we consider posted-price algorithms for the online metric matching problem. We give an $O(\log n)$-competitive posted-price randomized algorithm in the case that the metric space is a line. In p
Externí odkaz:
http://arxiv.org/abs/2310.12394
We consider the online transportation problem set in a metric space containing parking garages of various capacities. Cars arrive over time, and must be assigned to an unfull parking garage upon their arrival. The objective is to minimize the aggrega
Externí odkaz:
http://arxiv.org/abs/2307.08832
We consider the online $k$-median clustering problem in which $n$ points arrive online and must be irrevocably assigned to a cluster on arrival. As there are lower bound instances that show that an online algorithm cannot achieve a competitive ratio
Externí odkaz:
http://arxiv.org/abs/2303.15379
We consider a class of optimization problems that involve determining the maximum value that a function in a particular class can attain subject to a collection of difference constraints. We show that a particular linear programming technique, based
Externí odkaz:
http://arxiv.org/abs/2211.08381
We show that there exist $k$-colorable matroids that are not $(b,c)$-decomposable when $b$ and $c$ are constants. A matroid is $(b,c)$-decomposable, if its ground set of elements can be partitioned into sets $X_1, X_2, \ldots, X_l$ with the following
Externí odkaz:
http://arxiv.org/abs/2206.12896
This paper considers the basic problem of scheduling jobs online with preemption to maximize the number of jobs completed by their deadline on $m$ identical machines. The main result is an $O(1)$ competitive deterministic algorithm for any number of
Externí odkaz:
http://arxiv.org/abs/2111.06564
Many tasks use data housed in relational databases to train boosted regression tree models. In this paper, we give a relational adaptation of the greedy algorithm for training boosted regression trees. For the subproblem of calculating the sum of squ
Externí odkaz:
http://arxiv.org/abs/2107.12373
Our main contribution is a polynomial-time algorithm to reduce a $k$-colorable gammoid to a $(2k-2)$-colorable partition matroid. It is known that there are gammoids that can not be reduced to any $(2k-3)$-colorable partition matroid, so this result
Externí odkaz:
http://arxiv.org/abs/2107.03795
We consider the problem of efficiently estimating the size of the inner join of a collection of preprocessed relational tables from the perspective of instance optimality analysis. The run time of instance optimal algorithms is comparable to the mini
Externí odkaz:
http://arxiv.org/abs/2012.08083