The proceedings contain 25 papers. The special focus in this conference is on theory and practice of algorithms in (computer) systems. The topics include: A comparison of three algorithms for approximating the distanc...
ISBN:
(纸本)9783642197536
The proceedings contain 25 papers. The special focus in this conference is on theory and practice of algorithms in (computer) systems. The topics include: A comparison of three algorithms for approximating the distance distribution in real-world graphs;exploiting bounded signal flow for graph orientation based on cause–effect Pairs;on greedy and submodular matrices;MIP formulations for flowshop scheduling with limited buffers;a scenario-based approach for robust linear optimization;conflict propagation and component recursion for canonical labeling;3-hitting set on bounded degree hypergraphs: Upper and lower bounds on the kernel size;improved taxation rate for bin packing games;multi-channel assignment for communication in radio networks;managing power heterogeneity;computing strongly connected components in the streaming model;improved approximation algorithms for the max-edge coloring problem;new bounds for old algorithms: On the average-case behavior of classic single-source shortest-paths approaches;an approximative criterion for the potential of energetic reasoning;speed scaling for energy and performance with instantaneous parallelism;algorithms for scheduling with power control in wireless networks;the mathematics of mobility;speed scaling to manage temperature;alternative route graphs in road networks;robust line planning in case of multiple pools and disruptions;exact algorithms for intervalizing colored graphs;l(2,1)-labeling of unigraphs;energy-efficient due date scheduling.
The aim of this invited talk is to try to stimulate research in the interesting and promising research direction of distributed verification. This distributed bears some similarities to the task of solving decision pr...
详细信息
ISBN:
(纸本)9783642197536
The aim of this invited talk is to try to stimulate research in the interesting and promising research direction of distributed verification. This distributed bears some similarities to the task of solving decision problems in the context of sequential computing. There, the study of decision problems proved very fruitful in establishing structured foundations for the theory. There are some signs that the study of distributed verification may be fruitful for the theory of distributed computing too.
In the INTERVALIZING COLORED GRAPHS problem, one must decide for a given graph G = (V, E) with a proper vertex coloring of G whether G is the subgraph of a properly colored interval graph. For the case that the number...
详细信息
ISBN:
(纸本)9783642197536
In the INTERVALIZING COLORED GRAPHS problem, one must decide for a given graph G = (V, E) with a proper vertex coloring of G whether G is the subgraph of a properly colored interval graph. For the case that the number of colors k is fixed, we give an exact algorithm that uses O* (2(n/log1-epsilon) (n),) time for all epsilon > 0. We also give an O*(2(n)) algorithm for the case that the number of colors k is not fixed.
Finding robust solutions of an optimization problem is an important issue in practice. The established concept of Ben-Tal et al. [2] requires that a robust solution is feasible for all possible scenarios. However, thi...
详细信息
ISBN:
(纸本)9783642197536
Finding robust solutions of an optimization problem is an important issue in practice. The established concept of Ben-Tal et al. [2] requires that a robust solution is feasible for all possible scenarios. However, this concept is very conservative and hence may lead to solutions with a bad objective value and is in many cases hard to solve. Thus it is not suitable for most practical applications. In this paper we suggest an algorithm for calculating robust solutions that is easy to implement and not as conservative as the strict robustness approach. We show some theoretical properties of our approach and evaluate it using linear programming problems from NetLib.
We consider the speed scaling problem where the quality of service objective is deadline feasibility and the power objective is temperature. In the case of batched jobs, we give a simple algorithm to compute the optim...
详细信息
ISBN:
(纸本)9783642197536
We consider the speed scaling problem where the quality of service objective is deadline feasibility and the power objective is temperature. In the case of batched jobs, we give a simple algorithm to compute the optimal schedule. For general instances, we give a new online algorithm, and obtain an upper bound on the competitive ratio of this algorithm that is an order of magnitude better than the best previously known bound upper bound on the competitive ratio for this problem.
The proceedings contain 24 papers. The topics discussed include: distributed decision problems: the locality angle;managing power heterogeneity;the mathematics of mobility;speed scaling to manage temperature;alternati...
ISBN:
(纸本)9783642197536
The proceedings contain 24 papers. The topics discussed include: distributed decision problems: the locality angle;managing power heterogeneity;the mathematics of mobility;speed scaling to manage temperature;alternative route graphs in road networks;robust line planning in case of multiple pools and disruptions;exact algorithms for intervalizing colored graphs;energy-efficient due date scheduling;go with the flow: the direction-based fŕechet distance of polygonal curves;a comparison of three algorithms for approximating the distance distribution in real-world graphs;exploiting bounded signal flow for graph orientation based on cause-effect pairs;on greedy and submodular matrices;a scenario-based approach for robust linear optimization;conflict propagation and component recursion for canonical labeling;improved taxation rate for bin packing games;and multi-channel assignment for communication in radio networks.
The L(2,1)-labeling problem consists of assigning colors from the integer set 0, ... , lambda to the nodes of a graph G in such a way that nodes at a distance of at most two get different colors, while adjacent nodes ...
详细信息
ISBN:
(纸本)9783642197536
The L(2,1)-labeling problem consists of assigning colors from the integer set 0, ... , lambda to the nodes of a graph G in such a way that nodes at a distance of at most two get different colors, while adjacent nodes get colors which are at least two apart. The aim of this problem is to minimize A and it is in general NP-complete. In this paper the problem of L(2, 1)-labeling unigraphs, i.e. graphs uniquely determined by their own degree sequence up to isomorphism, is addressed and a 3/2-approximate algorithm for L(2, 1)-labeling unigraphs is designed. This algorithm runs in O(n) time, improving the time of the algorithm based on the greedy technique, requiring O(m) time, that may be near to Theta(n(2)) for unigraphs.
Despite disillusioning worst-case behavior, classic algorithms for single-source shortest-paths (SSSP) like Bellman-Ford are still being used in practice, especially due to their simple data structures. However, surpr...
详细信息
ISBN:
(纸本)9783642197536
Despite disillusioning worst-case behavior, classic algorithms for single-source shortest-paths (SSSP) like Bellman-Ford are still being used in practice, especially due to their simple data structures. However, surprisingly little is known about the average-case complexity of these approaches. We provide new theoretical and experimental results for the performance of classic label-correcting SSSP algorithms on graph classes with non-negative random edge weights. In particular, we prove a tight lower bound of Omega(n(2)) for the running times of Bellman-Ford on a class of sparse graphs with O(n) nodes and edges;the best previous bound was Omega(n(4/3-epsilon)). The same improvements are shown for Pallottino's algorithm. We also lift a lower bound for the approximate bucket implementation of Dijkstra's algorithm from Omega(n log n/log log n) to Omega(n(1.2-epsilon)). Furthermore, we provide an experimental evaluation of our new graph classes in comparison with previously used test inputs.
We extend the notions of functional and finiteness dependencies to apply to subsets of a relation that are specified by constraints. These dependencies have many applications. We are able to characterize those constra...
详细信息
We extend the notions of functional and finiteness dependencies to apply to subsets of a relation that are specified by constraints. These dependencies have many applications. We are able to characterize those constraint domains which admit a polynomial time solution of the implication problem (assuming P not equal NP) and give an efficient algorithm for these cases, module the cost of constraint manipulation. For other cases we offer approximate algorithms. Finally, we outline some applications of these dependencies to the analysis and optimization of CLP programs and database queries.
A model-based online fault-diagnosis scheme for an electromagnetically supported plate is presented as an example of a nonlinear and open-loop unstable system. First, residuals for sensor as well as for actuator fault...
详细信息
ISBN:
(纸本)9781467306737;9781467306720
A model-based online fault-diagnosis scheme for an electromagnetically supported plate is presented as an example of a nonlinear and open-loop unstable system. First, residuals for sensor as well as for actuator faults are generated using algebraic derivative estimators. Then, the robust detection and isolation of step-like sensor and actuator faults is presented. The performance of the proposed algorithms is illustrated by experimental results.
暂无评论