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.
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.
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.
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.
Local consistency has proven to be an important concept in the theory and practice of constraint networks. In this paper, we present a new definition of local consistency, called relational consistency. The new defini...
详细信息
Local consistency has proven to be an important concept in the theory and practice of constraint networks. In this paper, we present a new definition of local consistency, called relational consistency. The new definition is relation-based, in contrast with the previous definition of local consistency, which we characterize as variable-based. We show the conceptual power of the new definition by showing how it unifies known elimination operators such as resolution in theorem proving, joins in relational databases, and variable elimination for solving linear inequalities. algorithms for enforcing various levels of relational consistency are introduced and analyzed. We also show the usefulness of the new definition in characterizing relationships between properties of constraint networks and the level of local consistency needed to ensure global consistency.
This paper addresses the field of Artificial Intelligence, road it went so far and possible road it should go. The paper was invited by the conference of IT Revolutions 2008, and discusses some issues not emphasized i...
详细信息
ISBN:
(纸本)9783642039775
This paper addresses the field of Artificial Intelligence, road it went so far and possible road it should go. The paper was invited by the conference of IT Revolutions 2008, and discusses some issues not emphasized in AI trajectory so far. The recommendations are that the main focus should be personalities rather than programs or agents, that genetic environment should be introduced in reasoning about personalities, and that limbic system should be studied and modeled. Engineered Psychology is proposed as a road to go. Need for basic principles in psychology are discussed and a mathematical equation is proposed as fundamental law of engineered and human psychology.
暂无评论