Search

We study the maximum integral multicommodity flow problem and the minimum multicut problem restricted to trees. This restriction is quite rich and contains as special cases classical optimization problems such as matching and vertex cover for general graphs. It is shown that both the maximum integral multicommodity flow and the minimum multicut problem are NP-hard and MAX SNP-hard on trees, although the maximum integral flow can be computed in polynomial time if the edges have unit capacity. We present an efficient algorithm that computes a multicut and integral flow such that the weight of the multicut is at most twice the value of the flow. This gives a 2-approximation algorithm for minimum multicut and a 1/2-approximation algorithm for maximum integral multicommodity flow in trees.

We address the problem of performing simultaneously reachability analysis and minimization of real-time transition systems represented by timed automata, i.e., automata extended with a finite set of clock variables. The transitions of the automaton may depend on the values of the clocks and may reset some of the clocks. An efficient algorithm is presented for minimizing a system with respect to a given initial partition that respects the enabling conditions of the transitions of the timed automaton. Our algorithm generates the portion of the minimized system that is reachable from a given initial configuration in time polynomial in the input and the size of the minimal reachable system.

We consider a finite-state system with a finite number of clocks, where the transitions may depend on the values of the clocks, and may reset some of the clocks. We address the complexity and provide algorithms for the following problems. Suppose that the system starts from a given current state with a given assignment of values to the clocks. Can a given target state ever appear in the history of the system? What is the earliest time it can appear? What is the latest time it can appear?

This article addresses the problem of designing memory-efficient algorithms for the verification of temporal properties of finite-state programs. Both the programs and their desired temporal properties are modeled as automata on infinite words (Buchi automata). Verification is then reduced to checking the emptiness of the automaton resulting from the product of the program and the property. This problem is usually solved by computing the strongly connected components of the graph representing the product automaton. Here, we present algorithms that solve the emptiness problem without explicitly constructing the strongly connected components of the product graph. By allowing the algorithms to err with some probability, we can implement them with a randomly accessed memory of size O(n) bits, where n is the number of states of the graph, instead of O(n log n) bits that the presently known algorithms require.

We study a single-machine scheduling problem in which the items to be processed have to be batched as well as sequenced. Since processed items become available in batches, flow times are defined to be the same for all items in the same batch. A constant set-up delay is incurred between consecutive batches. For any fixed, but arbitrary item sequence, we present an algorithm that finds a sequence of batches such that the total flow time of the items is minimized; we prove that for a set ofn items, the algorithm runs inO(n) time. We show that, among all sequences, the one leading to the minimum flow time has the items in non-decreasing order of running times. Thus, the optimal algorithm for the combined problem, called thebatch-sizing problem, runs inO(n logn) time. We also prove that this algorithm yields an improved solution to a scheduling problem recently studied by Baker [1].

We give a simple proof that, determining whether a convex polytope has a fractional vertex, is NP-complete.