OpenRaiser/Intern-Atlas huggingface dataset:
Algorithmic Solutions to Some Transportation Optimization Problems with Applications in the Metallurgical Industry
Venue: arXiv cs.DS 2009
Year: 2009

In this paper we address several constrained transportation optimization problems (e.g. vehicle routing, shortest Hamiltonian path), for which we present novel algorithmic solutions and extensions, considering several optimization objectives, like minimizing costs and resource usage. All the considered problems are motivated by practical situations arising, for instance, in the mining and metallurgical industry or in data communication. We restrict our attention to transportation networks with path, tree or geometric structures, for which the developed polynomial-time algorithms are optimal or nearly optimal.
Optimal sparse CDMA detection at high load
Venue: arXiv cs.IT 2009
Year: 2009

Balancing efficiency of bandwidth use and complexity of detection involves choosing a suitable load for a multi-access channel. In the case of synchronous CDMA, with random codes, it is possible to demonstrate the existence of a threshold in the load beyond which there is an apparent jump in computational complexity. At small load unit clause propagation can determine a jointly optimal detection of sources on a noiseless channel, but fails at high load. Analysis provides insight into the difference between the standard dense random codes and sparse codes, and the limitations of optimal detection in the sparse case.
On generating independent random strings
Venue: arXiv cs.IT 2009
Year: 2009

It is shown that from two strings that are partially random and independent (in the sense of Kolmogorov complexity) it is possible to effectively construct polynomially many strings that are random and pairwise independent. If the two initial strings are random, then the above task can be performed in polynomial time. It is also possible to construct in polynomial time a random string, from two strings that have constant randomness rate.
Decentralized Management of Bi-modal Network Resources in a Distributed Stream Processing Platform
Venue: arXiv cs.DC 2009
Year: 2009

This paper presents resource management techniques for allocating communication and computational resources in a distributed stream processing platform. The platform is designed to exploit the synergy of two classes of network connections -- dedicated and opportunistic. Previous studies we conducted have demonstrated the benefits of such bi-modal resource organization that combines small pools of dedicated computers with a very large pool of opportunistic computing capacities of idle computers to serve high throughput computing applications. This paper extends the idea of bi-modal resource organization into the management of communication resources. Since distributed stream processing applications demand large volume of data transmission between processing sites at a consistent rate, adequate control over the network resources is important to assure a steady flow of processing. The system model used in this paper is a platform where stream processing servers at distributed sites are interconnected with a combination of dedicated and opportunistic communication links. Two pertinent resource allocation problems are analyzed in details and solved using decentralized algorithms. One is the mapping of the stream processing tasks on the processing and the communication resources. The other is the adaptive re-allocation of the opportunistic communication links due to the variations in their capacities. Overall optimization goal is higher task throughput and better utilization of the expensive dedicated links. The evaluation demonstrates that the algorithms are able to exploit the synergy of bi-modal communication links towards achieving the optimization goals.
Rate Adaptation via Link-Layer Feedback for Goodput Maximization over a Time-Varying Channel
Venue: arXiv cs.IT 2009
Year: 2009

We consider adapting the transmission rate to maximize the goodput, i.e., the amount of data transmitted without error, over a continuous Markov flat-fading wireless channel. In particular, we consider schemes in which transmitter channel state is inferred from degraded causal error-rate feedback, such as packet-level ACK/NAKs in an automatic repeat request (ARQ) system. In such schemes, the choice of transmission rate affects not only the subsequent goodput but also the subsequent feedback, implying that the optimal rate schedule is given by a partially observable Markov decision process (POMDP). Because solution of the POMDP is computationally impractical, we consider simple suboptimal greedy rate assignment and show that the optimal scheme would itself be greedy if the error-rate feedback was non-degraded. Furthermore, we show that greedy rate assignment using non-degraded feedback yields a total goodput that upper bounds that of optimal rate assignment using degraded feedback. We then detail the implementation of the greedy scheme and propose a reduced-complexity greedy scheme that adapts the transmission rate only once per block of packets. We also investigate the performance of the schemes numerically, and show that the proposed greedy scheme achieves steady-state goodputs that are reasonably close to the upper bound on goodput calculated using non-degraded feedback. A similar improvement is obtained in steady-state goodput, drop rate, and average buffer occupancy in the presence of data buffers. We also investigate an upper bound on the performance of optimal rate assignment for a discrete approximation of the channel and show that such quantization leads to a significant loss in achievable goodput.
On the Use of Suffix Arrays for Memory-Efficient Lempel-Ziv Data Compression
Venue: arXiv cs.DS 2009
Year: 2009

Much research has been devoted to optimizing algorithms of the Lempel-Ziv (LZ) 77 family, both in terms of speed and memory requirements. Binary search trees and suffix trees (ST) are data structures that have been often used for this purpose, as they allow fast searches at the expense of memory usage. In recent years, there has been interest on suffix arrays (SA), due to their simplicity and low memory requirements. One key issue is that an SA can solve the sub-string problem almost as efficiently as an ST, using less memory. This paper proposes two new SA-based algorithms for LZ encoding, which require no modifications on the decoder side. Experimental results on standard benchmarks show that our algorithms, though not faster, use 3 to 5 times less memory than the ST counterparts. Another important feature of our SA-based algorithms is that the amount of memory is independent of the text to search, thus the memory that has to be allocated can be defined a priori. These features of low and predictable memory requirements are of the utmost importance in several scenarios, such as embedded systems, where memory is at a premium and speed is not critical. Finally, we point out that the new algorithms are general, in the sense that they are adequate for applications other than LZ compression, such as text retrieval and forward/backward sub-string search.
Computer Systems to Oil Pipeline Transporting
Venue: arXiv cs.OH 2009
Year: 2009

Computer systems in the pipeline oil transporting that the greatest amount of data can be gathered, analyzed and acted upon in the shortest amount of time. Most operators now have some form of computer based monitoring system employing either commercially available or custom developed software to run the system. This paper presented the SCADA systems to oil pipeline in concordance to the Romanian environmental reglementations.
Design of Log-Map / Max-Log-Map Decoder
Venue: arXiv cs.IT 2009
Year: 2009

The process of turbo-code decoding starts with the formation of a posteriori probabilities (APPs) for each data bit, which is followed by choosing the data-bit value that corresponds to the maximum a posteriori (MAP) probability for that data bit. Upon reception of a corrupted code-bit sequence, the process of decision making with APPs allows the MAP algorithm to determine the most likely information bit to have been transmitted at each bit time.
FISLAB - the Fuzzy Inference Tool-box for SCILAB
Venue: arXiv cs.MS 2009
Year: 2009

The present study represents "The Fislab package of programs meant to develop the fuzzy regulators in the Scilab environment" in which we present some general issues, usage requirements and the working mode of the Fislab environment. In the second part of the article some features of the Scilab functions from the Fislab package are described.
The development of a fuzzy regulator with an entry and an output in Fislab
Venue: arXiv cs.MS 2009
Year: 2009

The present article is a sequel of the article "Fislab the Fuzzy Inference Tool-Box for Scilab" and it represents the practical application of:"The development of the Fuzzy regulator with an input and an output in Fislab". The article contains, besides this application, some functions to be used in the program, namely Scilab functions for the fuzzification of the firm information, functions for the operation of de-fuzzification and functions for the implementation of.
Ranking Functions for Size-Change Termination II
Venue: arXiv cs.LO 2009
Year: 2009

Size-Change Termination is an increasingly-popular technique for verifying program termination. These termination proofs are deduced from an abstract representation of the program in the form of "size-change graphs". We present algorithms that, for certain classes of size-change graphs, deduce a global ranking function: an expression that ranks program states, and decreases on every transition. A ranking function serves as a witness for a termination proof, and is therefore interesting for program certification. The particular form of the ranking expressions that represent SCT termination proofs sheds light on the scope of the proof method. The complexity of the expressions is also interesting, both practicaly and theoretically. While deducing ranking functions from size-change graphs has already been shown possible, the constructions in this paper are simpler and more transparent than previously known. They improve the upper bound on the size of the ranking expression from triply exponential down to singly exponential (for certain classes of instances). We claim that this result is, in some sense, optimal. To this end, we introduce a framework for lower bounds on the complexity of ranking expressions and prove exponential lower bounds.
Computer- and robot-assisted Medical Intervention
Venue: arXiv cs.RO 2009
Year: 2009

Medical robotics includes assistive devices used by the physician in order to make his/her diagnostic or therapeutic practices easier and more efficient. This chapter focuses on such systems. It introduces the general field of Computer-Assisted Medical Interventions, its aims, its different components and describes the place of robots in that context. The evolutions in terms of general design and control paradigms in the development of medical robots are presented and issues specific to that application domain are discussed. A view of existing systems, on-going developments and future trends is given. A case-study is detailed. Other types of robotic help in the medical environment (such as for assisting a handicapped person, for rehabilitation of a patient or for replacement of some damaged/suppressed limbs or organs) are out of the scope of this chapter.
On the Achievable Diversity-Multiplexing Tradeoff in MIMO Fading Channels with Imperfect CSIT
Venue: arXiv cs.IT 2009
Year: 2009

In this paper, we analyze the fundamental tradeoff of diversity and multiplexing in multi-input multi-output (MIMO) channels with imperfect channel state information at the transmitter (CSIT). We show that with imperfect CSIT, a higher diversity gain as well as a more efficient diversity-multiplexing tradeoff (DMT) can be achieved. In the case of multi-input single-output (MISO)/single-input multi-output (SIMO) channels with K transmit/receive antennas, one can achieve a diversity gain of d(r)=K(1-r+Kα) at spatial multiplexing gain r, where αis the CSIT quality defined in this paper. For general MIMO channels with M (M>1) transmit and N (N>1) receive antennas, we show that depending on the value of α, different DMT can be derived and the value of αhas a great impact on the achievable diversity, especially at high multiplexing gains. Specifically, when αis above a certain threshold, one can achieve a diversity gain of d(r)=MN(1+MNα)-(M+N-1)r; otherwise, the achievable DMT is much lower and can be described as a collection of discontinuous line segments depending on M, N, r and α. Our analysis reveals that imperfect CSIT significantly improves the achievable diversity gain while enjoying high spatial multiplexing gains.
A computational method for bounding the probability of reconstruction on trees
Venue: arXiv cs.DM 2009
Year: 2009

For a tree Markov random field non-reconstruction is said to hold if as the depth of the tree goes to infinity the information that a typical configuration at the leaves gives about the value at the root goes to zero. The distribution of the measure at the root conditioned on a typical boundary can be computed using a distributional recurrence. However the exact computation is not feasible because the support of the distribution grows exponentially with the depth. In this work, we introduce a notion of a survey of a distribution over probability vectors which is a succinct representation of the true distribution. We show that a survey of the distribution of the measure at the root can be constructed by an efficient recursive algorithm. The key properties of surveys are that the size does not grow with the depth, they can be constructed recursively, and they still provide a good bound for the distance between the true conditional distribution and the unconditional distribution at the root. This approach applies to a large class of Markov random field models including randomly generated ones. As an application we show bounds on the reconstruction threshold for the Potts model on small-degree trees.
Learning Multiple Belief Propagation Fixed Points for Real Time Inference
Venue: arXiv cs.LG 2009
Year: 2009

In the context of inference with expectation constraints, we propose an approach based on the "loopy belief propagation" algorithm LBP, as a surrogate to an exact Markov Random Field MRF modelling. A prior information composed of correlations among a large set of N variables, is encoded into a graphical model; this encoding is optimized with respect to an approximate decoding procedure LBP, which is used to infer hidden variables from an observed subset. We focus on the situation where the underlying data have many different statistical components, representing a variety of independent patterns. Considering a single parameter family of models we show how LBP may be used to encode and decode efficiently such information, without solving the NP hard inverse problem yielding the optimal MRF. Contrary to usual practice, we work in the non-convex Bethe free energy minimization framework, and manage to associate a belief propagation fixed point to each component of the underlying probabilistic mixture. The mean field limit is considered and yields an exact connection with the Hopfield model at finite temperature and steady state, when the number of mixture components is proportional to the number of variables. In addition, we provide an enhanced learning procedure, based on a straightforward multi-parameter extension of the model in conjunction with an effective continuous optimization procedure. This is performed using the stochastic search heuristic CMAES and yields a significant improvement with respect to the single parameter basic model.
TCP over 3G links: Problems and Solutions
Venue: arXiv cs.NI 2009
Year: 2009

This review paper presents analytical information regarding the transfer of TCP data flows on paths towards interconnected wireless systems, with emphasis on 3G cellular networks. The focus is on protocol modifications in face of problems arising from terminal mobility and wireless transmission. The objective of this paper is not to present an exhaustive review of the literature, but to filter out the causes of poor TCP performance in such systems and give a rationalized view of measures that can be taken against them.
Efficient Description Logic Reasoning in Prolog: The DLog system
Venue: arXiv cs.LO 2009
Year: 2009

This paper describes a resolution based Description Logic reasoning system called DLog. DLog transforms Description Logic axioms into a Prolog program and uses the standard Prolog execution for efficiently answering instance retrieval queries. From the Description Logic point of view, DLog is an ABox reasoning engine for the full SHIQ language. The DLog approach makes it possible to store the individuals in a database instead of memory, which results in better scalability and helps using description logic ontologies directly on top of existing information sources. To appear in Theory and Practice of Logic Programming (TPLP).
Controller synthesis with very simplified linear constraints in PN model
Venue: arXiv cs.IT 2009
Year: 2009

This paper addresses the problem of forbidden states for safe Petri net modeling discrete event systems. We present an efficient method to construct a controller. A set of linear constraints allow forbidding the reachability of specific states. The number of these so-called forbidden states and consequently the number of constraints are large and lead to a large number of control places. A systematic method for constructing very simplified controller is offered. By using a method based on Petri nets partial invariants, maximal permissive controllers are determined.
Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities
Venue: arXiv cs.CC 2009
Year: 2009

We prove that the problem of computing an Arrow-Debreu market equilibrium is PPAD-complete even when all traders use additively separable, piecewise-linear and concave utility functions. In fact, our proof shows that this market-equilibrium problem does not have a fully polynomial-time approximation scheme unless every problem in PPAD is solvable in polynomial time.
Effect of cell residence time variance on the performance of an advanced paging algorithm
Venue: arXiv cs.PF 2009
Year: 2009

The use of advanced sequential paging algorithms has been suggested as a means to reduce the signaling cost in future mobile cellular networks. In a proposed algorithm (Koukoutsidis and Theologou, 2003), the system can use the additional information of the last interaction cell combined with a mobility model to predict the short-term location probabilities at the time of an incoming call arrival. The short-term location probabilities reduce the uncertainty in mobile user position and thus greatly improve the search. In this paper, an analytical model is derived that allows for a general distribution of cell residence times. By considering a Gamma distribution, we study the effect of the variance of cell residence times and derive useful results on the performance of the algorithm.
Usinage de poches en UGV - Aide au choix de stratégies
Venue: arXiv cs.OH 2009
Year: 2009

The paper deals with associating the optimal machining strategy to a given pocket geometry, within the context of High-Speed Machining (HSM) of aeronautical pockets. First we define different classes of pocket features according to geometrical criteria. Following, we propose a method allowing to associate a set of capable tools to the features. Each capable tool defines a machined zone with a specific geometry. The last part of the paper is thus dedicated to associate the optimal machining strategy to a given geometry within the context of HSM. Results highlight that analyses must be conducted in a dynamical as well as a geometrical viewpoint. In particular, it becomes necessary to integrate dynamical specifities associated to the behavior of the couple machine/NC unit in the tool path calculation.
Learning convex bodies is hard
Venue: arXiv cs.LG 2009
Year: 2009

We show that learning a convex body in $\RR^d$, given random samples from the body, requires $2^{Ω(\sqrt{d/\eps})}$ samples. By learning a convex body we mean finding a set having at most $\eps$ relative symmetric difference with the input body. To prove the lower bound we construct a hard to learn family of convex bodies. Our construction of this family is very simple and based on error correcting codes.
On the Communication of Scientific Results: The Full-Metadata Format
Venue: arXiv cs.DL 2009
Year: 2009

In this paper, we introduce a scientific format for text-based data files, which facilitates storing and communicating tabular data sets. The so-called Full-Metadata Format builds on the widely used INI-standard and is based on four principles: readable self-documentation, flexible structure, fail-safe compatibility, and searchability. As a consequence, all metadata required to interpret the tabular data are stored in the same file, allowing for the automated generation of publication-ready tables and graphs and the semantic searchability of data file collections. The Full-Metadata Format is introduced on the basis of three comprehensive examples. The complete format and syntax is given in the appendix.
Reducibility Among Fractional Stability Problems
Venue: arXiv cs.CC 2009
Year: 2009

In this paper, we resolve the computational complexity of a number of outstanding open problems with practical applications. Here is the list of problems we show to be PPAD-complete, along with the domains of practical significance: Fractional Stable Paths Problem (FSPP) [21] - Internet routing; Core of Balanced Games [41] - Economics and Game theory; Scarf's Lemma [41] - Combinatorics; Hypergraph Matching [1]- Social Choice and Preference Systems; Fractional Bounded Budget Connection Games (FBBC) [30] - Social networks; and Strong Fractional Kernel [2]- Graph Theory. In fact, we show that no fully polynomial-time approximation schemes exist (unless PPAD is in FP). This paper is entirely a series of reductions that build in nontrivial ways on the framework established in previous work. In the course of deriving these reductions, we created two new concepts - preference games and personalized equilibria. The entire set of new reductions can be presented as a lattice with the above problems sandwiched between preference games (at the "easy" end) and personalized equilibria (at the "hard" end). Our completeness results extend to natural approximate versions of most of these problems. On a technical note, we wish to highlight our novel "continuous-to-discrete" reduction from exact personalized equilibria to approximate personalized equilibria using a linear program augmented with an exponential number of "min" constraints of a specific form. In addition to enhancing our repertoire of PPAD-complete problems, we expect the concepts and techniques in this paper to find future use in algorithmic game theory.