368077
Approximation of Walrasian equilibrium in single-minded auctions
We consider a social optimization model of pricing scheme in single-minded auctions, in cases where Walrasian equilibrium does not exist. We are interested in the maximization of the ratio, R, of happy bidders over all agents, in a feasible allocation-pricing scheme. We show NP-hardness of the optimization problem, establish lower and upper bounds of R, as well as develop greedy algorithms to approximate the optimal value of R.
751784
An Efficient Algorithm for Computing Optimal Discrete Voltage Schedules
We consider the problem of job scheduling on a variable voltage processor with d discrete voltage/speed levels. We give an algorithm which constructs a minimum energy schedule for n jobs in O(dnlogn) time. Previous approaches solve this problem by first computing the optimal continuous solution in O(n 3 ) time and then adjusting the speed to discrete levels. In our approach, the optimal discrete solution is characterized and computed directly from the inputs. We also show that O(n log n) time is required, hence the algorithm is optimal for fixed d.
20792301
An Efficient Algorithm for Computing Optimal Discrete Voltage Schedules
We consider the problem of job scheduling on a variable voltage processor with d discrete voltage/speed levels. We give an algorithm which constructs a minimum energy schedule for n jobs in O(dnlog n) time. Previous approaches solve this problem by first computing the optimal continuous solution in O(n3) time and then adjusting the speed to discrete levels. In our approach, the optimal discrete solution is characterized and computed directly from the inputs. We also show that O(nlog n) time is required, hence the algorithm is optimal for fixed d.
3605809
Performance evaluation for energy efficient topologic control in ad hoc wireless networks
Minimizing total energy to keep an ad hoc wireless network symmetrically connected is an NP-hard problem. Recently, several greedy approximations have been proposed, based on k-restricted decompositions of the network. Their performance ratios are established through estimations of the least upper bound ρk for the ratio between total powers of best possible k-restricted decomposition and the optimal solution. In this paper, we determine the exact value of ρk for all k.
5801265
Reversibility and adiabatic computation: trading time and space for energy
Future miniaturization and mobilization of computing devices requires energy parsimonious ‘adiabatic’ computation. This is contingent on logical reversibility of computation. An example is the idea of quantum computations which are reversible except for the irreversible observation steps. We propose to study quantitatively the exchange of computational resources like time and space for irreversibility in computations. Reversible simulations of irreversible computations are memory intensive. Such (polynomial time) simulations are analysed here in terms of ‘reversible’ pebble games. We show that Bennett’s pebbling strategy uses least additional space for the greatest number of simulated steps. We derive a trade-off for storage space versus irreversible erasure. Next we consider reversible computation itself. An alternative proof is provided for the precise expression of the ultimate irreversibility cost of an otherwise reversible computation without restrictions on time and space use. A time-irreversibility trade-off hierarchy in the exponential time region is exhibited. Finally, extreme time-irreversibility trade-offs for reversible computations in the thoroughly unrealistic range of computable versus non-computable time-bounds are given.
52151541
Linear approximation of shortest superstrings
We consider the following problem: given a collection of strings <italic>s<subscrpt>1</subscrpt></italic>,…, <italic>s<subscrpt>m</subscrpt></italic>, find the shortest string <italic>s</italic> such that each <italic>s<subscrpt>i</subscrpt></italic> appears as a substring (a consecutive block) of <italic>s</italic>. Although this problem is known to be NP-hard, a simple greedy procedure appears to do quite well and is routinely used in DNA sequencing and data compression practice, namely: repeatedly merge the pair of (distinct) strings with maximum overlap until only one string remains. Let <italic>n</italic> denote the length of the optimal superstring. A common conjecture states that the above greedy procedure produces a superstring of length <italic>O(n)</italic> (in fact, 2<italic>n</italic>), yet the only previous nontrivial bound known for any polynomial-time algorithm is a recent <italic>O(n</italic> log <italic>n</italic>) result.
We show that the greedy algorithm does in fact achieve a constant factor approximation, proving an upper bound of 4<italic>n</italic>. Furthermore, we present a simple modified version of the greedy algorithm that we show produces a superstring of length at most 3<italic>n</italic>. We also show the superstring problem to be MAXSNP-hard, which implies that a polynomial-time approximation scheme for this problem is unlikely.
41518374
Longest cycles in regular 2-connected claw-free graphs
In this paper, we show that every 2-connected, k-regular claw-free graph on n vertices contains a cycle of length at least min 4k?2, n (k?8), and this result is best possible.
16584711
PeerWindow: an efficient, heterogeneous, and autonomic node collection protocol
Nodes in peer-to-peer systems need to know the information about others to optimize neighbor selection, resource exchanging, replica placement, load balancing, query optimization, and other collaborative operations. However, how to collect this information effectively is still an open issue. In this paper, we propose a novel information collection protocol, PeerWindow, with which each node can collect a large amount of pointers to other nodes at a very low cost. Compared to existing protocols, PeerWindow is 1) efficient, the cost of collecting 1,000 pointers being less than 1 kbps in a common system environment, 2) heterogeneous, nodes with different capacities collecting different amounts of information, and 3) autonomic, nodes determining their bandwidth cost for node collection by themselves and adjusting it dynamically. PeerWindow can be used in many existing peer-to-peer systems and has tremendous potential for future expansions.