Greed is good: Approximating independent sets in sparse and bounded-degree graphs

Theminimum-degree greedy algorithm, or Greedy for short, is a simple and well-studied method for finding independent sets in graphs. We show that it achieves a performance ratio of (Δ+2)/3 for approximating independent sets in graphs with degree bounded by Δ. The analysis yields a precise characterization of the size of the independent sets found by the algorithm as a function of the independence number, as well as a generalization of Turán’s bound. We also analyze the algorithm when run in combination with a known preprocessing technique, and obtain an improved performance ratio on graphs with average degree , improving on the previous best of Hochbaum. Finally, we present an efficient parallel and distributed algorithm attaining the performance guarantees of Greedy. Gordon Gekko [29]. A preliminary version of this paper appeared at the 26th ACM Symposium on Theory of Computing, 1994. This work was done while both authors were at the Japan Advanced Institute of Science and Technology, Hokuriku.     

Detection of fouling in a cross-flow heat exchanger using a neural network based technique

This paper presents a method for the detection of fouling in a cross-flow heat exchanger. A numerical model is used to generate data when the heat exchanger is clean and corresponding data when fouling occurs. In a first step, the model is used to generate a long time series by simulating a clean heat exchanger. This allows the determination of a neural network model of the heat exchanger. Then, hundred sets of data are generated by simulating a fouled heat exchanger and it is checked that the simple Cusum test can be used to detect fouling without any false alarm, whatever the reference time series is.     

Speckle reduction in laser projection systems by diffractive optical elements

In laser projection systems the observer in the far field of the image points on the screen will recognize serious speckle noise. There are many methods to reduce or eliminate speckles in the near field by reducing or eliminating temporal or spatial coherence of the laser. But for the far field it is hardly possible to change the coherence properties of laser sources so that speckles will disappear. We propose a new method for eliminating speckles in the far field by using a diffractive optical element. The intensity modulation depth in the far-field speckle pattern can be reduced to a few percent while good beam quality is preserved.     

On spectrum sharing games

Efficient spectrum-sharing mechanisms are crucial to alleviate the bandwidth limitation in wireless networks. In this paper, we consider the following question: can free spectrum be shared efficiently? We study this problem in the context of 802.11 or WiFi networks. Each access point (AP) in a WiFi network must be assigned a channel for it to service users. There are only finitely many possible channels that can be assigned. Moreover, neighboring access points must use different channels so as to avoid interference. Currently these channels are assigned by administrators who carefully consider channel conflicts and network loads. Channel conflicts among APs operated by different entities are currently resolved in an ad hoc manner (i.e., not in a coordinated way) or not resolved at all. We view the channel assignment problem as a game, where the players are the service providers and APs are acquired sequentially. We consider the price of anarchy of this game, which is the ratio between the total coverage of the APs in the worst Nash equilibrium of the game and what the total coverage of the APs would be if the channel assignment were done optimally by a central authority. We provide bounds on the price of anarchy depending on assumptions on the underlying network and the type of bargaining allowed between service providers. The key tool in the analysis is the identification of the Nash equilibria with the solutions to a maximal coloring problem in an appropriate graph. We relate the price of anarchy of these games to the approximation factor of local optimization algorithms for the maximum k-colorable subgraph problem. We also study the speed of convergence in these games.     

Sum Coloring Interval and k -Claw Free Graphs with Application to Scheduling Dependent Jobs

We consider the sum coloring and sum multicoloring problems on several fundamental classes of graphs, including the classes of interval and k-claw free graphs. We give an algorithm that approximates sum coloring within a factor of 1.796, for any graph in which the maximum k-colorable subgraph problem is polynomially solvable. In particular, this improves on the previous best known ratio of 2 for interval graphs. We introduce a new measure of coloring, robust throughput}, that indicates how quickly the graph is colored, and show that our algorithm approximates this measure within a factor of 1.4575. In addition, we study the contiguous (or non-preemptive) sum multicoloring problem on k-claw free graphs. This models, for example, the scheduling of dependent jobs on multiple dedicated machines, where each job requires the exclusive use of at most k machines. Assuming that k is a fixed constant, we obtain the first constant factor approximation for the problem.     

Nearly optimal bounds for distributed wireless scheduling in the SINR model

We study the wireless scheduling problem in the SINR model. More specifically, given a set of \(n\) links, each a sender–receiver pair, we wish to partition (or schedule) the links into the minimum number of slots, each satisfying interference constraints allowing simultaneous transmission. In the basic problem, all senders transmit with the same uniform power. We analyze a randomized distributed scheduling algorithm proposed by Kesselheim and Vöcking, and show that it achieves \(O(\log n)\)-approximation, an improvement of a logarithmic factor. This matches the best ratio known for centralized algorithms and holds in arbitrary metric space and for every length-monotone and sublinear power assignment. We also show that every distributed algorithm uses \(\varOmega (\log n)\) slots to schedule certain instances that require only two slots, which implies that the best possible absolute performance guarantee is logarithmic.     

The double electrostatic ion ring experiment: a unique cryogenic electrostatic storage ring for merged ion-beams studies

We describe the design of a novel type of storage device currently under construction at Stockholm University, Sweden, using purely electrostatic focussing and deflection elements, in which ion beams of opposite charges are confined under extreme high vacuum cryogenic conditions in separate "rings" and merged over a common straight section. The construction of this double electrostatic ion ring experiment uniquely allows for studies of interactions between cations and anions at low and well-defined internal temperatures and centre-of-mass collision energies down to about 10 K and 10 meV, respectively. Position sensitive multi-hit detector systems have been extensively tested and proven to work in cryogenic environments and these will be used to measure correlations between reaction products in, for example, electron-transfer processes. The technical advantages of using purely electrostatic ion storage devices over magnetic ones are many, but the most relevant are: electrostatic elements which are more compact and easier to construct; remanent fields, hysteresis, and eddy-currents, which are of concern in magnetic devices, are no longer relevant; and electrical fields required to control the orbit of the ions are not only much easier to create and control than the corresponding magnetic fields, they also set no upper mass limit on the ions that can be stored. These technical differences are a boon to new areas of fundamental experimental research, not only in atomic and molecular physics but also in the boundaries of these fields with chemistry and biology. For examples, studies of interactions with internally cold molecular ions will be particular useful for applications in astrophysics, while studies of solvated ionic clusters will be of relevance to aeronomy and biology.