Search results for " Complexity"
showing 10 items of 623 documents
Team Theory and Person-by-Person Optimization with Binary Decisions
2012
In this paper, we extend the notion of person-by-person (pbp) optimization to binary decision spaces. The novelty of our approach is the adaptation to a dynamic team context of notions borrowed from the pseudo-boolean optimization field as completely local-global or unimodal functions and submodularity. We also generalize the concept of pbp optimization to the case where groups of $m$ decisions makers make joint decisions sequentially, which we refer to as $m$b$m$ optimization. The main contribution is a description of sufficient conditions, verifiable in polynomial time, under which a pbp or an $m$b$m$ optimization algorithm converges to the team-optimum. As a second contribution, we prese…
On the approximability of the range assignment problem on radio networks in presence of selfish agents
2005
AbstractWe consider the range assignment problem in ad-hoc wireless networks in the context of selfish agents: A network manager aims to assigning transmission ranges to the stations in order to achieve strong connectivity of the network within a minimal overall power consumption. Station is not directly controlled by the manager and may refuse to transmit with a certain transmission range because it might be costly in terms of power consumption.We investigate the existence of payment schemes which induce the stations to follow the decisions of a network manager in computing a range assignment, that is, truthful mechanisms for the range assignment problem. We provide both positive and negat…
A note on the separation of subtour elimination constraints in elementary shortest path problems
2013
Abstract This note proposes an alternative procedure for identifying violated subtour elimination constraints (SECs) in branch-and-cut algorithms for elementary shortest path problems. The procedure is also applicable to other routing problems, such as variants of travelling salesman or shortest Hamiltonian path problems, on directed graphs. The proposed procedure is based on computing the strong components of the support graph. The procedure possesses a better worst-case time complexity than the standard way of separating SECs, which uses maximum flow algorithms, and is easier to implement.
Robust control of uncertain multi-inventory systems via linear matrix inequality
2008
We consider a continuous time linear multi inventory system with unknown demands bounded within ellipsoids and controls bounded within ellipsoids or polytopes. We address the problem of "-stabilizing the inventory since this implies some reduction of the inventory costs. The main results are certain conditions under which "-stabilizability is possible through a saturated linear state feedback control. All the results are based on a Linear Matrix Inequalities (LMIs) approach and on some recent techniques for the modeling and analysis of polytopic systems with saturations.
Decomposition of Dynamic Single-Product and Multi-product Lotsizing Problems and Scalability of EDAs
2008
In existing theoretical and experimental work, Estimation of Distribution Algorithms (EDAs) are primarily applied to decomposable test problems. State-of-the-art EDAs like the Hierarchical Bayesian Optimization Algorithm (hBOA), the Learning Factorized Distribution Algorithm (LFDA) or Estimation of Bayesian Networks Algorithm (EBNA) solve these problems in polynomial time. Regarding this success, it is tempting to apply EDAs to real-world problems. But up to now, it has rarely been analyzed which real-world problems are decomposable. The main contribution of this chapter is twofold: (1) It shows that uncapacitated single-product and multi-product lotsizing problems are decomposable. (2) A s…
Optimal Switches in Multi–inventory Systems
2007
Given a switched multi-inventory system we wish to find the optimal schedule of the resets to maintain the system in a safe operating interval, while minimizing a function related to the cost of the resets. We discuss a family of instances that can be solved in polynomial time by linear programming. We do this by introducing a set-covering formulation with a totally unimodular constraint matrix.
A fast recursive algorithm for the computation of axial moments
2002
This paper describes a fast algorithm to compute local axial moments used for the detection of objects of interest in images. The basic idea is grounded on the elimination of redundant operations while computing axial moments for two neighboring angles of orientation. The main result is that the complexity of recursive computation of axial moments becomes independent of the total number of computed moments in a given point, i.e. it is of the order O(N) where N is the data size. This result is of great importance in computer vision since many feature extraction methods are based on the computation of axial moments. The experimental results confirm the time complexity and accuracy predicted b…
Parallel Simulated Annealing: Getting Super Linear Speedups
2005
The study described in this paper tries to improve and combine different approaches that are able to speed up applications of the Simulated Annealing model. It investigates separately two main aspects concerning the degree of parallelism an implementation can egectively exploit at the initial andfinal periods of an execution. As for case studies, it deals with two implementations: the Job shop Scheduling problem and the poryblio selection problem. The paper reports the results of a large number of experiments, carried out by means of a transputer network and a hypercube system. They give useful suggestions about selecting the most suitable values of the intervention parameters to achieve su…
The Reconstruction of Polyominoes from Approximately Orthogonal Projections
2001
The reconstruction of discrete two-dimensional pictures from their projection is one of the central problems in the areas of medical diagnostics, computer-aided tomography, pattern recognition, image processing, and data compression. In this note, we determine the computational complexity of the problem of reconstruction of polyominoes from their approximately orthogonal projections. We will prove that it is NP-complete if we reconstruct polyominoes, horizontal convex polyominoes and vertical convex polyominoes. Moreover we will give the polynomial algorithm for the reconstruction of hv-convex polyominoes that has time complexity O(m3n3).
Mappings of finite distortion: The sharp modulus of continuity
2003
We establish an essentially sharp modulus of continuity for mappings of subexponentially integrable distortion.