| 1. |
- Damaschke, Peter, 1963
(författare)
-
Optimizing a mail-order with discount and shipping costs
- 2002
-
Ingår i: Information Processing Letters. - 0020-0190. ; 82:2, s. 93-97
-
Tidskriftsartikel (refereegranskat)abstract
- We address the problem of minimizing the total cost of a mail-order if a customer can choose among different companies. These companies may offer the items in his shopping list at different prices, and they add some charges or give discount, depending on the total value of ordered goods. While this optimization problem is hard in general, we show that it can be efficiently solved for some typical discount policies, either exactly or by invoking an approximation scheme for the Knapsack problem.
|
|
| 2. |
- Fomin, Fedor V., et al.
(författare)
-
Approximation algorithms for time-dependent orienteering
- 2002
-
Ingår i: Information Processing Letters. - 0020-0190. ; 83:2, s. 57-62
-
Tidskriftsartikel (refereegranskat)abstract
- The time-dependent orienteering problem is dual to the time-dependent traveling salesman problem. It consists of visiting a maximum number of sites within a given deadline. The traveling time between two sites is in general dependent on the starting time. For ε greater than or equal 0, we provide a (2+ ε)-approximation algorithm for the time-dependent orienteering problem which runs in polynomial time if the ratio between the maximum and minimum traveling time between any two sites is constant. No prior upper approximation bounds were known for this time-dependent problem.
|
|
| 3. |
- Gasieniec, Leszek, et al.
(författare)
-
On adaptive deterministic gossiping in ad hoc radio networks
- 2002
-
Ingår i: Information Processing Letters. - 0020-0190. ; 83:2, s. 89-93, s. 689-690
-
Tidskriftsartikel (refereegranskat)abstract
- We study deterministic algorithms for gossiping problem in ad hoc radio networks. The efficiency of communication algorithms in radio networks is very often expressed in terms of: maximum eccentricity D, maximum in-degree &DELTA;, and size (number of nodes) n of underlying graph of connections. The maximum eccentricity D of a network is the maximum of the lengths of shortest directed paths from a node u to a node v, taken over all ordered pairs (u,v) of nodes in the network. The maximum in-degree &DELTA; of a network is the maximum of in-degrees of its nodes.We propose a new method that leads to several improvements in deterministic gossiping. It combines communication techniques designed for both known as well as unknown ad hoc radio networks. First we show how to subsume the O(Dn)-time bound yield by the round-robin procedure proposing a new O(Dn)-time gossiping algorithm.11Notation O(f(n)) stands for O(f(n). logcn), for any constant c>0. Our algorithm is more efficient than the known O(n3/2)-time gossiping algorithms [Proc. 41st IEEE Symp. on Found. of Computer Science, 2000, pp. 575-581; Proc. 13th ACM-SIAM Symp. on Discrete Algorithms, 2002], whenever D=O(nα) and α<1. For large values of maximum eccentricity D, we give another gossiping algorithm that works in time O(D&DELTA;3/2log3n) which subsumes the O(D&DELTA;2log3n) upper bound presented in [Proc. 20th ACM Symp. on Principles of Distributed Computing, 2001, pp. 255-263]. Finally, we observe that for any so-called oblivious (i.e., non-adaptive) deterministic gossiping algorithm, any natural n and 1=
|
|
| 4. |
- Gudmundsson, J, et al.
(författare)
-
Lower bounds for approximate polygon decomposition and minimum gap
- 2002
-
Ingår i: Information Processing Letters. - 0020-0190. ; 81:3, s. 137-141
-
Tidskriftsartikel (refereegranskat)abstract
- We consider the problem of decomposing polygons (with holes) into various types of simpler polygons. We focus on the problem of partitioning a rectilinear polygon, with holes, into rectangles, and show an Omega (n log n) lower bound on the time-complexity. The result holds for any decomposition, optimal or approximative. The bound matches the complexity of a number of algorithms in the literature, proving their optimality and settling the complexity of approximate polygon decomposition in these cases. As a related result we show that any non-trivial approximation algorithm for the minimum gap problem requires Omega (n log n) time. (C) 2002 Elsevier Science B.V. All rights reserved.
|
|
| 5. |
|
|
| 6. |
|
|
| 7. |
- Carlsson, Svante, et al.
(författare)
-
An optimal parallel adaptive sorting algorithm
- 1991
-
Ingår i: Information Processing Letters. - 0020-0190 .- 1872-6119. ; 39:4, s. 195-200
-
Tidskriftsartikel (refereegranskat)abstract
- We consider the problem of designing optimal parallel algorithms for sorting presorted sequences. To evaluate the existing order in an input sequence, we use the number of the maximal ascending consecutive subsequences, Runs. in the sequence as a measure of presortedness. An adaptive parallel sorting algorithm is presented, which sorts a sequence X of length n inO(logn·log Runs(X)) time by using ... processors in the EREW PRAM model of computation. It is the first adaptive parallel sorting algorithm that is cost optimal with respect to Runs.
|
|
| 8. |
|
|
| 9. |
- Holenderski, Leszek, et al.
(författare)
-
Propositional Description of Finite Cause-Effect Structures
- 1988
-
Ingår i: Information Processing Letters. - : Elsevier. - 0020-0190 .- 1872-6119. ; 27:3, s. 111-117
-
Tidskriftsartikel (refereegranskat)abstract
- An alternative method of describing semantics of cause-effect structures is presented. It is based on a model of discrete dynamic systems. The model is similar to a condition-event Petri net, differing in the way restrictions on the alterability of actions are imposed.
|
|
| 10. |
- Håstad, Johan
(författare)
-
On bounded occurrence constraint satisfaction
- 2000
-
Ingår i: Information Processing Letters. - 0020-0190 .- 1872-6119. ; 74:02-jan, s. 1-6
-
Tidskriftsartikel (refereegranskat)abstract
- An approximation algorithm for a constraint satisfaction problem is said to be nontrivial if its performance ratio is strictly superior to the expected performance of the algorithm which simply chooses a random assignment. We prove that any constraint satisfaction problem where each variable appears a bounded number of times admits a nontrivial polynomial time approximation algorithm.
|
|
