| 1. |
- Coquand, Thierry, 1961
(författare)
-
A syntactical proof of the marriage lemma
- 2003
-
Ingår i: Theoretical Computer Science. - 0304-3975. ; 290:1, s. 1107-1113
-
Tidskriftsartikel (refereegranskat)abstract
- We give a proof of the classical Marriage Lemma (Amer. J. Math. 72 (1950) 214) using completeness of hyperresolution. This argument is purely syntactical, and extends directly to the infinite case. As an application we give a purely syntactical version of a proof that resolution is exponential on the pigeon-hole principle.
|
|
| 2. |
- Damaschke, Peter, 1963
(författare)
-
Nearly optimal strategies for special cases of on-line capital investment
- 2003
-
Ingår i: Theoretical Computer Science. - 0304-3975. ; 302:1, s. 35-44
-
Tidskriftsartikel (refereegranskat)abstract
- Suppose that some job must be done for a period of unspecified duration. The market offers a selection of devices that can do this job, each characterized by purchase and running costs. Which of them should we buy at what times, in order to minimize the total costs? As usual in competitive analysis, the cost of an on-line solution is compared to the optimum costs paid by a clearvoyant buyer. This problem which generalizes the basic rent-to-buy problem has been introduced by Y. Azar et al. In the so-called convex case where lower running costs always imply higher prices, a strategy with competitive ratio 6.83 has been proposed. Here we consider two naturalsubcases of the convex case in a continuous-time model where new devices can be bought at any time. For the static case where all devices are available at the beginning, we give a simple 4-competitive deterministic algorithm, and we show that 3.618 is a lower bound. (This is also the first non-trivial lower bound for the convex case, both for discrete and continuous time.) Furthermore we give a 2.88-competitive randomized algorithm. In the case that all devices have equal prices but are not all available at the beginning, we show that a very simple algorithm is 2-competitive, and we derive a 1.618 lower bound.
|
|
| 3. |
- Damaschke, Peter, 1963
(författare)
-
Online strategies for backups
- 2002
-
Ingår i: Theoretical Computer Science. - 0304-3975. ; 285:1, s. 43-53
-
Tidskriftsartikel (refereegranskat)abstract
- We consider strategies for backups from the viewpoint of competitive analysis of online problems. We concentrate upon the realistic case that faults are rare, i.e. the cost of work between two faults is typically large compared to the cost of one backup. Instead of the (worst-case) competitive ratio we use a refined and more expressive quality measure, in terms of the average fault frequency. The interesting matter is, roughly speaking, to adapt the backup frequency to the fault frequency, while future faults are unpredictable. We give an asymptotically optimal deterministic strategy and propose a randomized strategy whose expected cost beats the deterministic bound.
|
|
| 4. |
- Damaschke, Peter, 1963
(författare)
-
Two short notes on the on-line traveling salesman: handling times and lookahead
- 2002
-
Ingår i: Theoretical Computer Science. - 0304-3975. ; 289:1, s. 845-852
-
Tidskriftsartikel (refereegranskat)abstract
- We study extensions of the on-line travelling salesman problem. Our results are: The optimal competitive ratio 2 for arbitrary metric spaces also holds in the case of nonzero handling times. The optimal competitive ratio 3/2 on the half-line cannot be improved by randomization, but there is a 4/3-competitive algorithm under the assumption that the server is notified when the last request has been released. This ratio is also optimal.
|
|
| 5. |
- Dybjer, Peter, 1953
(författare)
-
Some results on the deductive structure of join dependencies
- 1984
-
Ingår i: Theoretical Computer Science. - : Elsevier BV. - 0304-3975. ; 33:1, s. 95-105
-
Tidskriftsartikel (refereegranskat)abstract
- Among the many different data dependencies defined, the so-called join dependencies play a central role, since they explicitly capture lossless join properties for relation schemes. In this paper we state some inference rules for join dependencies and embedded join dependencies. A set of two rules is shown to be complete for monadic join dependency inferences (inferences from a single dependency). Furthermore, it is shown that there is no finite set of inference rules that is complete for embedded join dependencies.
|
|
| 6. |
- Krznaric, Drago, et al.
(författare)
-
Optimal algorithms for complete linkage clustering in d dimensions
- 2002
-
Ingår i: Theoretical Computer Science. - 0304-3975. ; 286:1, s. 139-149
-
Konferensbidrag (refereegranskat)abstract
- It is shown that the complete linkage clustering of n points in R-d, where d greater than or equal to 1 is a constant, can be computed in optimal O(nlogn) time and linear space, under the L-1 and L-infinity-metrics. Furthermore, for every other fixed L-t-metric, it is shown that it can be approximated within an arbitrarily small constant factor in O(nlogn) time and linear space.
|
|
| 7. |
|
|
| 8. |
- Alimonti, P., et al.
(författare)
-
Some APX-completeness results for cubic graphs
- 2000
-
Ingår i: Theoretical Computer Science. - 0304-3975 .- 1879-2294. ; 237:2-Jan, s. 123-134
-
Tidskriftsartikel (refereegranskat)abstract
- Four fundamental graph problems, Minimum vertex cover, Maximum independent set, Minimum dominating set and Maximum cut, are shown to be APX-complete even for cubic graphs. Therefore, unless P = NP, these problems do not admit any polynomial time approximation scheme on input graphs of degree bounded by three.
|
|
| 9. |
- Carlsson, Svante, et al.
(författare)
-
Heaps with bits
- 1996
-
Ingår i: Theoretical Computer Science. - : Elsevier BV. - 0304-3975 .- 1879-2294. ; 164:1-2, s. 1-12
-
Tidskriftsartikel (refereegranskat)abstract
- We show how to improve the complexity of heap operations and heapsort using extra bits. We first study the parallel complexity of implementing priority queue operations on a heap. The tradeoff between the number of extra bits used, the number of processors available, and the parallel time complexity is derived. While inserting a new element into a heap in parallel can be done as fast as parallel searching in a sorted list, we show how to delete the smallest element from a heap in constant time with a sublinear number of processors, and in sublogarithmic time with a sublogarithmic number of processors. The models of parallel computation used are the CREW PRAM and the CRCW PRAM. Our results improve those of previously known algorithms. Moreover, we study a variant, the fine heap, of the traditional heap structure. A fast algorithm for constructing this new data structure is designed using an interesting technique, which is also used to develop an improved heapsort algorithm. Our variation of heapsort is faster than I. Wegener's (1993) heapsort and requires less extra space.
|
|
| 10. |
- Engebretsen, Lars, et al.
(författare)
-
Inapproximability results for equations over finite groups
- 2004
-
Ingår i: Theoretical Computer Science. - 0304-3975 .- 1879-2294. ; 312:1, s. 17-45
-
Tidskriftsartikel (refereegranskat)abstract
- An equation over a finite group G is an expression of form w(1)w(2). . .w(k) = 1(G), where each w(i) is a variable, an inverted variable, or a constant from G; such an equation is satisfiable if there is a setting of the variables to values in G so that the equality is realized. We study the problem of simultaneously satisfying a family of equations over a finite group G and show that it is NP-hard to approximate the number of simultaneously satisfiable equations to within \G\ - epsilon for any epsilon > 0. This generalizes results of Hastad (J. ACM 48 (4) (2001) 798), who established similar bounds under the added condition that the group G is Abelian.
|
|
