OpenRaiser/Intern-Atlas huggingface dataset:
Bin packing with general cost structures
Venue: arXiv cs.DS 2009
Year: 2009

Following the work of Anily et al., we consider a variant of bin packing, called "bin packing with general cost structures" (GCBP) and design an asymptotic fully polynomial time approximation scheme (AFPTAS) for this problem. In the classic bin packing problem, a set of one-dimensional items is to be assigned to subsets of total size at most 1, that is, to be packed into unit sized bins. However, in GCBP, the cost of a bin is not 1 as in classic bin packing, but it is a non-decreasing and concave function of the number of items packed in it, where the cost of an empty bin is zero. The construction of the AFPTAS requires novel techniques for dealing with small items, which are developed in this work. In addition, we develop a fast approximation algorithm which acts identically for all non-decreasing and concave functions, and has an asymptotic approximation ratio of 1.5 for all functions simultaneously.
General combination rules for qualitative and quantitative beliefs
Venue: arXiv cs.AI 2009
Year: 2009

Martin and Osswald \cite{Martin07} have recently proposed many generalizations of combination rules on quantitative beliefs in order to manage the conflict and to consider the specificity of the responses of the experts. Since the experts express themselves usually in natural language with linguistic labels, Smarandache and Dezert \cite{Li07} have introduced a mathematical framework for dealing directly also with qualitative beliefs. In this paper we recall some element of our previous works and propose the new combination rules, developed for the fusion of both qualitative or quantitative beliefs.
Comments on "A new combination of evidence based on compromise" by K. Yamada
Venue: arXiv cs.CV 2009
Year: 2009

Comments on ``A new combination of evidence based on compromise'' by K. Yamada
Asymptotically Optimal Policies for Hard-deadline Scheduling over Fading Channels
Venue: arXiv cs.IT 2009
Year: 2009

A hard-deadline, opportunistic scheduling problem in which $B$ bits must be transmitted within $T$ time-slots over a time-varying channel is studied: the transmitter must decide how many bits to serve in each slot based on knowledge of the current channel but without knowledge of the channel in future slots, with the objective of minimizing expected transmission energy. In order to focus on the effects of delay and fading, we assume that no other packets are scheduled simultaneously and no outage is considered. We also assume that the scheduler can transmit at capacity where the underlying noise channel is Gaussian such that the energy-bit relation is a Shannon-type exponential function. No closed form solution for the optimal policy is known for this problem, which is naturally formulated as a finite-horizon dynamic program, but three different policies are shown to be optimal in the limiting regimes where $T$ is fixed and $B$ is large, $T$ is fixed and $B$ is small, and where $B$ and $T$ are simultaneously taken to infinity. In addition, the advantage of optimal scheduling is quantified relative to a non-opportunistic (i.e., channel-blind) equal-bit policy.
A Note on Mathematical Modelling of Practical Multicampaign Assignment and Its Computational Complexity
Venue: arXiv cs.CC 2009
Year: 2009

Within personalized marketing, a recommendation issue known as multicampaign assignment is to overcome a critical problem, known as the multiple recommendation problem which occurs when running several personalized campaigns simultaneously. This paper mainly deals with the hardness of multicampaign assignment, which is treated as a very challenging problem in marketing. The objective in this problem is to find a customer-campaign matrix which maximizes the effectiveness of multiple campaigns under some constraints. We present a realistic response suppression function, which is designed to be more practical, and explain how this can be learned from historical data. Moreover, we provide a proof that this more realistic version of the problem is NP-hard, thus justifying to use of heuristics presented in previous work.
Teaching Quality Assurance and Project Management to Undergraduate Computing Students in Pakistan
Venue: arXiv cs.CY 2009
Year: 2009

Software Project Management (SPM) and Software Quality Assurance (SQA) are key components of undergraduate Computing programmes at educational establishments in Pakistan. Because of the nature of these subjects, there are a number of issues that need to be discussed and resolved so that the teaching becomes more effective, students learning experience is more enjoyable and their ability to be actively involved in SPM and SQA, after the completion of their studies, becomes further improved. In this paper, we discuss experience of teaching SPM and SQA at one particular institution in Islamabad Pakistan. Using this as a case study, we underline the students perspective, highlight the inherent issues and suggest ways to improve the delivery of these subjects. Since, the issues are mainly generic, the aim is to provide discussion and recommendations to benefit a wider computing community in academia.
A note on syndeticity, recognizable sets and Cobham's theorem
Venue: arXiv cs.FL 2009
Year: 2009

In this note, we give an alternative proof of the following result. Let p, q >= 2 be two multiplicatively independent integers. If an infinite set of integers is both p- and q-recognizable, then it is syndetic. Notice that this result is needed in the classical proof of the celebrated Cobham?s theorem. Therefore the aim of this paper is to complete [13] and [1] to obtain an accessible proof of Cobham?s theorem.
On the complexity of deciding whether the distinguishing chromatic number of a graph is at most two
Venue: arXiv cs.CC 2009
Year: 2009

In an article [3] published recently in this journal, it was shown that when k >= 3, the problem of deciding whether the distinguishing chromatic number of a graph is at most k is NP-hard. We consider the problem when k = 2. In regards to the issue of solvability in polynomial time, we show that the problem is at least as hard as graph automorphism but no harder than graph isomorphism.
Tight Bounds for Online Stable Sorting
Venue: arXiv cs.DS 2009
Year: 2009

Although many authors have considered how many ternary comparisons it takes to sort a multiset $S$ of size $n$, the best known upper and lower bounds still differ by a term linear in $n$. In this paper we restrict our attention to online stable sorting and prove upper and lower bounds that are within (o (n)) not only of each other but also of the best known upper bound for offline sorting. Specifically, we first prove that if the number of distinct elements (σ= o (n / \log n)), then ((H + 1) n + o (n)) comparisons are sufficient, where $H$ is the entropy of the distribution of the elements in $S$. We then give a simple proof that ((H + 1) n - o (n)) comparisons are necessary in the worst case.
A generalized inner and outer product of arbitrary multi-dimensional arrays using A Mathematics of Arrays (MoA)
Venue: arXiv cs.MS 2009
Year: 2009

An algorithm has been devised to compute the inner and outer product between two arbitrary multi-dimensional arrays A and B in a single piece of code. It was derived using A Mathematics of Arrays (MoA) and the $ψ$-calculus. Extensive tests of the new algorithm are presented for running in sequential as well as OpenMP multiple processor modes.
A Bayesian Model for Supervised Clustering with the Dirichlet Process Prior
Venue: arXiv cs.LG 2009
Year: 2009

We develop a Bayesian framework for tackling the supervised clustering problem, the generic problem encountered in tasks such as reference matching, coreference resolution, identity uncertainty and record linkage. Our clustering model is based on the Dirichlet process prior, which enables us to define distributions over the countably infinite sets that naturally arise in this problem. We add supervision to our model by positing the existence of a set of unobserved random variables (we call these "reference types") that are generic across all clusters. Inference in our framework, which requires integrating over infinitely many parameters, is solved using Markov chain Monte Carlo techniques. We present algorithms for both conjugate and non-conjugate priors. We present a simple--but general--parameterization of our model based on a Gaussian assumption. We evaluate this model on one artificial task and three real-world tasks, comparing it against both unsupervised and state-of-the-art supervised algorithms. Our results show that our model is able to outperform other models across a variety of tasks and performance metrics.
ChOrDa: a methodology for the modeling of business processes with BPMN
Venue: arXiv cs.SE 2009
Year: 2009

In this paper we present a modeling methodology for BPMN, the standard notation for the representation of business processes. Our methodology simplifies the development of collaborative BPMN diagrams, enabling the automated creation of skeleton process diagrams representing complex choreographies. To evaluate and tune the methodology, we have developed a tool supporting it, that we apply to the modeling of an international patenting process as a working example.
How Controlled English can Improve Semantic Wikis
Venue: arXiv cs.HC 2009
Year: 2009

The motivation of semantic wikis is to make acquisition, maintenance, and mining of formal knowledge simpler, faster, and more flexible. However, most existing semantic wikis have a very technical interface and are restricted to a relatively low level of expressivity. In this paper, we explain how AceWiki uses controlled English - concretely Attempto Controlled English (ACE) - to provide a natural and intuitive interface while supporting a high degree of expressivity. We introduce recent improvements of the AceWiki system and user studies that indicate that AceWiki is usable and useful.
How to Evaluate Controlled Natural Languages
Venue: arXiv cs.HC 2009
Year: 2009

This paper presents a general framework how controlled natural languages can be evaluated and compared on the basis of user experiments. The subjects are asked to classify given statements (in the language to be tested) as either true or false with respect to a certain situation that is shown in a graphical notation called "ontographs". A first experiment has been conducted that applies this framework to the language Attempto Controlled English (ACE).
Distributed Random Access Algorithm: Scheduling and Congesion Control
Venue: arXiv cs.IT 2009
Year: 2009

This paper provides proofs of the rate stability, Harris recurrence, and epsilon-optimality of CSMA algorithms where the backoff parameter of each node is based on its backlog. These algorithms require only local information and are easy to implement. The setup is a network of wireless nodes with a fixed conflict graph that identifies pairs of nodes whose simultaneous transmissions conflict. The paper studies two algorithms. The first algorithm schedules transmissions to keep up with given arrival rates of packets. The second algorithm controls the arrivals in addition to the scheduling and attempts to maximize the sum of the utilities of the flows of packets at the different nodes. For the first algorithm, the paper proves rate stability for strictly feasible arrival rates and also Harris recurrence of the queues. For the second algorithm, the paper proves the epsilon-optimality. Both algorithms operate with strictly local information in the case of decreasing step sizes, and operate with the additional information of the number of nodes in the network in the case of constant step size.
Online Sorting via Searching and Selection
Venue: arXiv cs.DS 2009
Year: 2009

In this paper, we present a framework based on a simple data structure and parameterized algorithms for the problems of finding items in an unsorted list of linearly ordered items based on their rank (selection) or value (search). As a side-effect of answering these online selection and search queries, we progressively sort the list. Our algorithms are based on Hoare's Quickselect, and are parameterized based on the pivot selection method. For example, if we choose the pivot as the last item in a subinterval, our framework yields algorithms that will answer q<=n unique selection and/or search queries in a total of O(n log q) average time. After q=Ω(n) queries the list is sorted. Each repeated selection query takes constant time, and each repeated search query takes O(log n) time. The two query types can be interleaved freely. By plugging different pivot selection methods into our framework, these results can, for example, become randomized expected time or deterministic worst-case time. Our methods are easy to implement, and we show they perform well in practice.
How discontinuous is Computing Nash Equilibria?
Venue: arXiv cs.GT 2009
Year: 2009

We investigate the degree of discontinuity of several solution concepts from non-cooperative game theory. While the consideration of Nash equilibria forms the core of our work, also pure and correlated equilibria are dealt with. Formally, we restrict the treatment to two player games, but results and proofs extend to the n-player case. As a side result, the degree of discontinuity of solving systems of linear inequalities is settled.
Simple Random Walks on Radio Networks (Simple Random Walks on Hyper-Graphs)
Venue: arXiv cs.NI 2009
Year: 2009

In recent years, protocols that are based on the properties of random walks on graphs have found many applications in communication and information networks, such as wireless networks, peer-to-peer networks and the Web. For wireless networks (and other networks), graphs are actually not the correct model of the communication; instead hyper-graphs better capture the communication over a wireless shared channel. Motivated by this example, we study in this paper random walks on hyper-graphs. First, we formalize the random walk process on hyper-graphs and generalize key notions from random walks on graphs. We then give the novel definition of radio cover time, namely, the expected time of a random walk to be heard (as opposed to visit) by all nodes. We then provide some basic bounds on the radio cover, in particular, we show that while on graphs the radio cover time is O(mn), in hyper-graphs it is O(mnr) where n, m and r are the number of nodes, the number of edges and the rank of the hyper-graph, respectively. In addition, we define radio hitting times and give a polynomial algorithm to compute them. We conclude the paper with results on specific hyper-graphs that model wireless networks in one and two dimensions.
Efficient Signal-Time Coding Design and its Application in Wireless Gaussian Relay Networks
Venue: arXiv cs.IT 2009
Year: 2009

Signal-time coding, which combines the traditional encoding/modulation mode in the signal domain with signal pulse phase modulation in the time domain, was proposed to improve the information flow rate in relay networks. In this paper, we mainly focus on the efficient signal-time coding design. We first derive an explicit iterative algorithm to estimate the maximum number of available codes given the code length of signal-time coding, and then present an iterative construction method of codebooks. It is shown that compared with conventional computer search, the proposed iterative construction method can reduce the complexity greatly. Numerical results will also indicate that the new constructed codebook is optimal in terms of coding rate. To minimize the buffer size needed to store the codebook while keeping a relatively high efficiency, we shall propose a combinatorial construction method. We will then consider applications in wireless Gaussian relay networks. It will be shown that in the three node network model, the mixed transmission by using two-hop and direct transmissions is not always a good option.
Classified Stable Matching
Venue: arXiv cs.DS 2009
Year: 2009

We introduce the {\sc classified stable matching} problem, a problem motivated by academic hiring. Suppose that a number of institutes are hiring faculty members from a pool of applicants. Both institutes and applicants have preferences over the other side. An institute classifies the applicants based on their research areas (or any other criterion), and, for each class, it sets a lower bound and an upper bound on the number of applicants it would hire in that class. The objective is to find a stable matching from which no group of participants has reason to deviate. Moreover, the matching should respect the upper/lower bounds of the classes. In the first part of the paper, we study classified stable matching problems whose classifications belong to a fixed set of ``order types.'' We show that if the set consists entirely of downward forests, there is a polynomial-time algorithm; otherwise, it is NP-complete to decide the existence of a stable matching. In the second part, we investigate the problem using a polyhedral approach. Suppose that all classifications are laminar families and there is no lower bound. We propose a set of linear inequalities to describe stable matching polytope and prove that it is integral. This integrality allows us to find various optimal stable matchings using Ellipsoid algorithm. A further ramification of our result is the description of the stable matching polytope for the many-to-many (unclassified) stable matching problem. This answers an open question posed by Sethuraman, Teo and Qian.
Bayesian Query-Focused Summarization
Venue: arXiv cs.CL 2009
Year: 2009

We present BayeSum (for ``Bayesian summarization''), a model for sentence extraction in query-focused summarization. BayeSum leverages the common case in which multiple documents are relevant to a single query. Using these documents as reinforcement for query terms, BayeSum is not afflicted by the paucity of information in short queries. We show that approximate inference in BayeSum is possible on large data sets and results in a state-of-the-art summarization system. Furthermore, we show how BayeSum can be understood as a justified query expansion technique in the language modeling for IR framework.
Learning Equilibria in Games by Stochastic Distributed Algorithms
Venue: arXiv cs.GT 2009
Year: 2009

We consider a class of fully stochastic and fully distributed algorithms, that we prove to learn equilibria in games. Indeed, we consider a family of stochastic distributed dynamics that we prove to converge weakly (in the sense of weak convergence for probabilistic processes) towards their mean-field limit, i.e an ordinary differential equation (ODE) in the general case. We focus then on a class of stochastic dynamics where this ODE turns out to be related to multipopulation replicator dynamics. Using facts known about convergence of this ODE, we discuss the convergence of the initial stochastic dynamics: For general games, there might be non-convergence, but when convergence of the ODE holds, considered stochastic algorithms converge towards Nash equilibria. For games admitting Lyapunov functions, that we call Lyapunov games, the stochastic dynamics converge. We prove that any ordinal potential game, and hence any potential game is a Lyapunov game, with a multiaffine Lyapunov function. For Lyapunov games with a multiaffine Lyapunov function, we prove that this Lyapunov function is a super-martingale over the stochastic dynamics. This leads a way to provide bounds on their time of convergence by martingale arguments. This applies in particular for many classes of games that have been considered in literature, including several load balancing game scenarios and congestion games.
Zero-error feedback capacity via dynamic programming
Venue: arXiv cs.IT 2009
Year: 2009

In this paper, we study the zero-error capacity for finite state channels with feedback when channel state information is known to both the transmitter and the receiver. We prove that the zero-error capacity in this case can be obtained through the solution of a dynamic programming problem. Each iteration of the dynamic programming provides lower and upper bounds on the zero-error capacity, and in the limit, the lower bound coincides with the zero-error feedback capacity. Furthermore, a sufficient condition for solving the dynamic programming problem is provided through a fixed-point equation. Analytical solutions for several examples are provided.
Layered Working-Set Trees
Venue: arXiv cs.DS 2009
Year: 2009

The working-set bound [Sleator and Tarjan, J. ACM, 1985] roughly states that searching for an element is fast if the element was accessed recently. Binary search trees, such as splay trees, can achieve this property in the amortized sense, while data structures that are not binary search trees are known to have this property in the worst case. We close this gap and present a binary search tree called a layered working-set tree that guarantees the working-set property in the worst case. The unified bound [Badoiu et al., TCS, 2007] roughly states that searching for an element is fast if it is near (in terms of rank distance) to a recently accessed element. We show how layered working-set trees can be used to achieve the unified bound to within a small additive term in the amortized sense while maintaining in the worst case an access time that is both logarithmic and within a small multiplicative factor of the working-set bound.
SMT-Based Bounded Model Checking for Embedded ANSI-C Software
Venue: arXiv cs.SE 2009
Year: 2009

Propositional bounded model checking has been applied successfully to verify embedded software but is limited by the increasing propositional formula size and the loss of structure during the translation. These limitations can be reduced by encoding word-level information in theories richer than propositional logic and using SMT solvers for the generated verification conditions. Here, we investigate the application of different SMT solvers to the verification of embedded software written in ANSI-C. We have extended the encodings from previous SMT-based bounded model checkers to provide more accurate support for finite variables, bit-vector operations, arrays, structures, unions and pointers. We have integrated the CVC3, Boolector, and Z3 solvers with the CBMC front-end and evaluated them using both standard software model checking benchmarks and typical embedded applications from telecommunications, control systems and medical devices. The experiments show that our approach can analyze larger problems and substantially reduce the verification time.
Multiresolution Elastic Medical Image Registration in Standard Intensity Scale
Venue: arXiv cs.CV 2009
Year: 2009

Medical image registration is a difficult problem. Not only a registration algorithm needs to capture both large and small scale image deformations, it also has to deal with global and local image intensity variations. In this paper we describe a new multiresolution elastic image registration method that challenges these difficulties in image registration. To capture large and small scale image deformations, we use both global and local affine transformation algorithms. To address global and local image intensity variations, we apply an image intensity standardization algorithm to correct image intensity variations. This transforms image intensities into a standard intensity scale, which allows highly accurate registration of medical images.
The Piranha algebraic manipulator
Venue: arXiv cs.SC 2009
Year: 2009

In this paper we present a specialised algebraic manipulation package devoted to Celestial Mechanics. The system, called Piranha, is built on top of a generic and extensible framework, which allows to treat efficiently and in a unified way the algebraic structures most commonly encountered in Celestial Mechanics (such as multivariate polynomials and Poisson series). In this contribution we explain the architecture of the software, with special focus on the implementation of series arithmetics, show its current capabilities, and present benchmarks indicating that Piranha is competitive, performance-wise, with other specialised manipulators.