"The activities, in project scheduling, can be represented graphically in two different ways, by either assigning the activities to the nodes 'AoN' directed acyclic graph (dag) or to the arcs 'AoA dag'. In this paper, a new algorithm is proposed for generating, for a given project scheduling problem, an Activity-on-Arc dag starting from the Activity-on-Node dag using the concepts of line graphs of graphs."

"...Common misconceptions regarding the embedding approach are addressed including whether or not it results in an average value control model (no), is necessary to "tweak" the algorithm to get bang-bang solutions (no), requires infinite switching (no), has real-time capability (yes), or reduction to a classical nonlinear optimization problem (a desirable yes)."

"This paper presents a study on two data structures that have been used to model several problems in computer science: and/or graphs and x-y graphs. An and/or graph is an acyclic digraph containing a source, such that every vertex v has a label f(v) in {and,or} and edges represent dependency relations between vertices: a vertex labeled and depends on all of its out-neighbors, while a vertex labeled or depends on only one of its out-neighbors. X-y graphs are defined as a natural generalization of and/or graphs: every vertex vi of an x-y graph has a label xi-yi to mean that vi depends on xi of its yi out-neighbors. We analyze the complexity of the optimization problems Min-and/or and Min-x-y, which consist of finding solution subgraphs of optimal weight for and/or and x-y graphs, respectively. Motivated by the large applicability as well as the hardness of Min-and/or and Min-x-y, we study new complexity aspects of such problems, both from a classical and a parameterized point of view. …"

"Block Sorting is a well studied problem, motivated by its applications in Optical Character Recognition (OCR), and Computational Biology. Block Sorting has been shown to be NP-Hard, and two separate polynomial time 2-approximation algorithms have been designed for the problem. But questions like whether a better approximation algorithm can be designed, and whether the problem is APX-Hard have been open for quite a while now.
In this work we answer the latter question by proving Block Sorting to be Max-SNP-Hard (APX-Hard). The APX-Hardness result is based on a linear reduction of Max-3SAT to Block Sorting. We also provide a new lower bound for the problem via a new parametrized problem k-Block Merging."

For the general problem of minimizing a convex function over a compact convex domain, we will investigate a simple iterative approximation algorithm based on the method by Frank & Wolfe 1956, that does not need projection steps in order to stay inside the optimization domain. Instead of a projection step, the linearized problem defined by a current subgradient is solved, which gives a step direction that will naturally stay in the domain. Our framework generalizes the sparse greedy algorithm of Frank & Wolfe and its primal-dual analysis by Clarkson 2010 (and the low-rank SDP approach by Hazan 2008) to arbitrary convex domains. We give a convergence proof guaranteeing {epsilon}-small duality gap after O(1/{epsilon}) iterations.

The method allows us to understand the sparsity of approximate solutions for any l1-regularized convex optimization problem (and for optimization over the simplex), expressed as a function of the approximation quality. We obtain matching upper and lower bounds of {Theta}(1/{epsilon}) for the sparsity for l1-problems. The same bounds apply to low-rank semidefinite optimization with bounded trace, showing that rank O(1/{epsilon}) is best possible here as well. As another application, we obtain sparse matrices of O(1/{epsilon}) non-zero entries as {epsilon}-approximate solutions when optimizing any convex function over a class of diagonally dominant symmetric matrices.

We show that our proposed first-order method also applies to nuclear norm and max-norm matrix optimization problems. For nuclear norm regularized optimization, such as matrix completion and low-rank recovery, we demonstrate the practical efficiency and scalability of our algorithm for large matrix problems, as e.g. the Netflix dataset. For general convex optimization over bounded matrix max-norm, our algorithm is the first with a convergence guarantee, to the best of our knowledge.

Several algorithms are available in the literature for finding the entire set of Pareto-optimal solutions in MultiObjective Linear Programming (MOLP). However, it has not been proposed so far an interior point algorithm that finds all Pareto-optimal solutions of MOLP. We present an explicit construction, based on a transformation of any MOLP into a finite sequence of SemiDefinite Programs (SDP), the solutions of which give the entire set of Pareto-optimal extreme points solutions of MOLP. These SDP problems are solved by interior point methods; thus our approach provides a pseudo-polynomial interior point methodology to find the set of Pareto-optimal solutions of MOLP.

"The k-domination number of a graph is the minimum size of a set X such that every vertex of G is in distance at most k from X. We give a linear time constant-factor approximation algorithm for k-domination number in classes of graphs with bounded expansion, which include e.g. proper minor-closed graph classes, classes closed on topological minors or classes of graphs that can be drawn on a fixed surface with bounded number of crossings on each edge.

The algorithm is based on the following approximate min-max characterization. A subset A of vertices of a graph G is d-independent if the distance between each pair of vertices in A is greater than d. Note that the size of the largest 2k-independent set is a lower bound for the k-domination number. We show that every graph from a fixed class with bounded expansion contains a 2k-independent set A and a k-dominating set D such that |D|=O(|A|), and these sets can be found in linear time. For domination number (k=1) the assumptions can be relaxed, and the result holds for all graph classes with arrangeability bounded by a constant."

"In the Partial Vertex Cover (PVC) problem we are given an undirected graph G = (V, E), a positive cost associated with each vertex and a positive integer k and the goal is to find a minimum cost subset of vertices S such that atleast k edges of the graph are covered. In this paper we consider two new generalization of the PVC problem. In the first variation which we call Partition Vertex Cover (Partition-VC) problem, the edges of the graph G are divided into n disjoint partitions $P_1, P_2... P_n$ and we have to select a minimum cost subset of vertices S such that atleast $k_i$ edges are covered from partition $P_i$. In the second variation which we call Knapsack Partition Vertex Cover (KPVC) problem, in addition to the previous conditions, each edge e has a profit $pi_{e}$ associated with it and we have an added knapsack constraint that the total profit of the covered edges in partition $P_i$ should be atleast $Pi_i$. We give an $O(log n)$ approximation for both the problems using a combination of deterministic rounding and randomized rounding approach that operates on the LP strengthened by adding Knapsack Cover inequalities as proposed by Carr, Fleischer, Leung & Phillips. We also show that these bounds can not be further improved by reducing the set cover problem to the Partition-VC problem in polynomial time. We also give an $O(f)$ approximation for the Partition-VC problem using a primal dual schema where f is the maximum number of edges in any partition."

"Efficient global optimization is the problem of minimizing an unknown function f, using as few evaluations f(x) as possible. It can be considered as a continuum-armed bandit problem, with noiseless data and simple regret. Expected improvement is perhaps the most popular method for solving this problem; the algorithm performs well in experiments, but little is known about its theoretical properties. Implementing expected improvement requires a choice of Gaussian process prior, which determines an associated space of functions, its reproducing-kernel Hilbert space (RKHS). When the prior is fixed, expected improvement is known to converge on the minimum of any function in the RKHS. We begin by providing convergence rates for this procedure. The rates are optimal for functions of low smoothness, and we modify the algorithm to attain optimal rates for smoother functions. For practitioners, however, these results are somewhat misleading. Priors are typically not held fixed, but depend on parameters estimated from the data. For standard estimators, we show this procedure may never discover the minimum of f. We then propose alternative estimators, chosen to minimize the constants in the rate of convergence, and show these estimators retain the convergence rates of a fixed prior."

"Let G = (V, E) be a directed acyclic graph with two distinguished vertices s, t and let F be a set of forbidden pairs of vertices. We say that a path in G is safe, if it contains at most one vertex from each pair {u, v} in F. Given G and F, the path avoiding forbidden pairs (PAFP) problem is to find a safe s-t path in G. We systematically study the complexity of different special cases of the PAFP problem defined according to the mutual positions of fobidden pairs. Fix one topological ordering of vertices; we say that pairs {u, v} and {x, y} are disjoint, if u, v < x, y, nested, if u < x, y < v, and halving, if u < x < v < y. The PAFP problem is known to be NP-hard in general or if no two pairs are disjoint; we prove that it remains NP-hard even when no two forbidden pairs are nested. On the other hand, if no two pairs are halving, the problem is known to be solvable in cubic time. We simplify and improve this result by showing an O(M(n)) time algorithm, where M(n) is the time to multiply two n times n boolean matrices."

"Optimal power flow (OPF) is an important problem for power generation and it is in general non-convex. With the employment of renewable energy, it will be desirable if OPF can be solved very efficiently so its solution can be used in real time. With some special network structure, e.g. trees, the problem has been shown to have a zero duality gap and the convex dual problem yields the optimal solution. In this paper, we propose a primal and a dual algorithm to coordinate the smaller subproblems decomposed from the convexified OPF. We can arrange the subproblems to be solved sequentially and cumulatively in a central node or solved in parallel in distributed nodes. We test the algorithms on IEEE radial distribution test feeders, some random tree-structured networks, and the IEEE transmission system benchmarks. Simulation results show that the computation time can be improved dramatically with our algorithms over the centralized approach of solving the problem without decomposition, especially in tree-structured problems. The computation time grows linearly with the problem size with the cumulative approach while the distributed one can have size-independent computation time."

"Internet-scale distributed systems such as content delivery networks (CDNs) operate hundreds of thousands of servers deployed in thousands of data center locations around the globe. Since the energy costs of operating such a large IT infrastructure are a significant fraction of the total operating costs, we argue for redesigning CDNs to incorporate energy optimizations as a first-order principle. We propose techniques to turn off CDN servers during periods of low load while seeking to balance three key design goals: maximize energy reduction, minimize the impact on client-perceived service availability (SLAs), and limit the frequency of on-off server transitions to reduce wear-and-tear and its impact on hardware reliability. We propose an optimal offline algorithm and an online algorithm to extract energy savings both at the level of local load balancing within a data center and global load balancing across data centers. We evaluate our algorithms using real production workload traces from a large commercial CDN. Our results show that it is possible to reduce the energy consumption of a CDN by more than 55% while ensuring a high level of availability that meets customer SLA requirements and incurring an average of one on-off transition per server per day. Further, we show that keeping even 10% of the servers as hot spares helps absorb load spikes due to global flash crowds with little impact on availability SLAs. Finally, we show that redistributing load across proximal data centers can enhance service availability significantly, but has only a modest impact on energy savings."

"This paper describes a new QR factorization algorithm which is especially designed for massively parallel platforms combining parallel distributed multi-core nodes. These platforms make the present and the foreseeable future of high-performance computing. Our new QR factorization algorithm falls in the category of the tile algorithms which naturally enables good data locality for the sequential kernels executed by the cores (high sequential performance), low number of messages in a parallel distributed setting (small latency term), and fine granularity (high parallelism)."

"Graph coloring is used in wireless networks to optimize network resources: bandwidth and energy. Nodes access the medium according to their color. It is the responsibility of the coloring algorithm to ensure that interfering nodes do not have the same color. In this research report, we focus on wireless sensor networks with grid topologies. How does a coloring algorithm take advantage of the regularity of grid topology to provide an optimal periodic coloring, that is a coloring with the minimum number of colors? We propose the Vector-Based Coloring Method, denoted VCM, a new method that is able to provide an optimal periodic coloring for any radio transmission range and for any h-hop coloring, h>=1. This method consists in determining at which grid nodes a color can be reproduced without creating interferences between these nodes while minimizing the number of colors used. We compare the number of colors provided by VCM with the number of colors obtained by a distributed coloring algorithm with line and column priority assignments. We also provide bounds on the number of colors of optimal general colorings of the infinite grid, and show that periodic colorings (and thus VCM) are asymptotically optimal. Finally, we discuss the applicability of this method to a real wireless network."

"We give the first polylogarithmic-competitive randomized online algorithm for the $k$-server problem on an arbitrary finite metric space. In particular, our algorithm achieves a competitive ratio of O(log^3 n log^2 k log log n) for any metric space on n points. Our algorithm improves upon the deterministic (2k-1)-competitive algorithm of Koutsoupias and Papadimitriou [J.ACM'95] whenever n is sub-exponential in k."

"The main cause of wasted energy consumption in wireless sensor networks is packet collision. The packet scheduling algorithm is therefore introduced to solve this problem. Some packet scheduling algorithms can also influence and delay the data transmitting in the real-time wireless sensor networks. This paper presents the packet scheduling algorithm (PSA) in order to reduce the packet congestion in MAC layer leading to reduce the overall of packet collision in the system The PSA is compared with the simple CSMA/CA and other approaches using network topology benchmarks in mathematical method. The performances of our PSA are better than the standard (CSMA/CA). The PSA produces better throughput than other algorithms. On other hand, the average delay of PSA is higher than previous works. However, the PSA utilizes the channel better than all algorithms."

"This paper addresses weight optimization problem in distributed consensus averaging algorithm over networks with symmetric star topology. We have determined optimal weights and convergence rate of the network in terms of its topological parameters. In addition, two alternative topologies with more rapid convergence rates have been introduced. The new topologies are Complete-Cored Symmetric (CCS) star and K-Cored Symmetric (KCS) star topologies. It has been shown that the optimal weights for the edges of central part in symmetric and CCS star configurations are independent of their branches. By simulation optimality of obtained weights under quantization constraints have been verified."

"At present there are a number of barriers to creating an energy efficient workload scheduler for a Private Cloud based data center. Firstly, the relationship between different workloads and power consumption must be investigated. Secondly, current hardware-based solutions to providing energy usage statistics are unsuitable in warehouse scale data centers where low cost and scalability are desirable properties. In this paper we discuss the effect of different workloads on server power consumption in a Private Cloud platform. We display a noticeable difference in energy consumption when servers are given tasks that dominate various resources (CPU, Memory, Hard Disk and Network). We then use this insight to develop CloudMonitor, a software utility that is capable of >95% accurate power predictions from monitoring resource consumption of workloads, after a "training phase" in which a dynamic power model is developed."

"Task reassignments in 2D mesh-connected systems (2D-MSs) have been researched and simulated for several decades. We propose a hierarchical 2D mesh-connected system (2D-HMS) in order to exploit the regular nature of a 2D-MS. In our approach priority-based task assignments and reassignments in a 2D-HMS are represented by tableaux and their algorithms. We provide examples of priority-based task reassignments in a 2D-HMS in which task relocations are simply reduced to a jeu de taquin slide."

"We develop a novel distributed algorithm for the minimum cut problem. We primarily aim at solving large sparse problems. Assuming vertices of the graph are partitioned into several regions, the algorithm performs path augmentations inside the regions and updates of the push-relabel style between the regions. The interaction between regions is considered expensive (regions are loaded into the memory one-by-one or located on separate machines in a network). The algorithm works in sweeps - passes over all regions. Let $B$ be the set of vertices incident to inter-region edges of the graph. We present a sequential and parallel versions of the algorithm which terminate in at most $2|B|^2+1$ sweeps. The competing algorithm by Delong and Boykov uses push-relabel updates inside regions. In the case of a fixed partition we prove that this algorithm has a tight $O(n^2)$ bound on the number of sweeps, where $n$ is the number of vertices. We tested sequential versions of the algorithms on instances of maxflow problems in computer vision. Experimentally, the number of sweeps required by the new algorithm is much lower than for the Delong and Boykov's variant. Large problems (up to $10^8$ vertices and $6cdot 10^8$ edges) are solved using under 1GB of memory in about 10 sweeps."

"We study a general class of PageRank optimization problems which consist in finding an optimal outlink strategy for a web site subject to design constraints. We consider both a continuous problem, in which one can choose the intensity of a link, and a discrete one, in which in each page, there are obligatory links, facultative links and forbidden links. We show that the continuous problem, as well as its discrete variant when there are no constraints coupling different pages, can both be modeled by constrained Markov decision processes with ergodic reward, in which the webmaster determines the transition probabilities of websurfers. Although the number of actions turns out to be exponential, we show that an associated polytope of transition measures has a concise representation, from which we deduce that the continuous problem is solvable in polynomial time, and that the same is true for the discrete problem when there are no coupling constraints. We also provide efficient algorithms, adapted to very large networks. Then, we investigate the qualitative features of optimal outlink strategies, and identify in particular assumptions under which there exists a "master" page to which all controlled pages should point. We report numerical results on fragments of the real web graph."

"We present algorithms for length-constrained maximum sum segment and maximum density segment problems, in particular, and the problem of finding length-constrained heaviest segments, in general, for a sequence of real numbers. Given a sequence of n real numbers and two real parameters L and U (L <= U), the maximum sum segment problem is to find a consecutive subsequence, called a segment, of length at least L and at most U such that the sum of the numbers in the subsequence is maximum. The maximum density segment problem is to find a segment of length at least L and at most U such that the density of the numbers in the subsequence is the maximum. For the first problem with non-uniform width there is an algorithm with time and space complexities in O(n). We present an algorithm with time complexity in O(n) and space complexity in O(U). For the second problem with non-uniform width there is a combinatorial solution with time complexity in O(n) and space complexity in O(U). We present a simple geometric algorithm with the same time and space complexities.

We extend our algorithms to respectively solve the length-constrained k maximum sum segments problem in O(n+k) time and O(max{U, k}) space, and the length-constrained $k$ maximum density segments problem in O(n min{k, U-L}) time and O(U+k) space. We present extensions of our algorithms to find all the length-constrained segments having user specified sum and density in O(n+m) and O(nlog (U-L)+m) times respectively, where m is the number of output. Previously, there was no known algorithm with non-trivial result for these problems. We indicate the extensions of our algorithms to higher dimensions. All the algorithms can be extended in a straight forward way to solve the problems with non-uniform width and non-uniform weight."

"Recent trends in planning research have led to empirical comparison becoming commonplace. The field has started to settle into a methodology for such comparisons, which for obvious practical reasons requires running a subset of planners on a subset of problems. In this paper, we characterize the methodology and examine eight implicit assumptions about the problems, planners and metrics used in many of these comparisons. The problem assumptions are: PR1) the performance of a general purpose planner should not be penalized/biased if executed on a sampling of problems and domains, PR2) minor syntactic differences in representation do not affect performance, and PR3) problems should be solvable by STRIPS capable planners unless they require ADL. The planner assumptions are: PL1) the latest version of a planner is the best one to use, PL2) default parameter settings approximate good performance, and PL3) time cut-offs do not unduly bias outcome. The metrics assumptions are: M1) performance degrades similarly for each planner when run on degraded runtime environments (e.g., machine platform) and M2) the number of plan steps distinguishes performance. We find that most of these assumptions are not supported empirically; in particular, that planners are affected differently by these assumptions. We conclude with a call to the community to devote research resources to improving the state of the practice and especially to enhancing the available benchmark problems."

"Suppose someone takes a solved 20x20x20 Rubik's cube and makes five moves - can you figure out [from that scrambled state] what those five moves were?" he asks. In other words, can you solve it in five moves? He suspects that you cannot, but has yet to prove it. "We don't know."

"We study the 2-dimensional vector packing problem, which is a generalization of the classical bin packing problem where each item has 2 distinct weights and each bin has 2 corresponding capacities. The goal is to group items into minimum number of bins, without violating the bin capacity constraints.…"

"The new algorithm by Yadava and his colleagues goes one step further. It uses a more realistic physics model of the x-ray source, the detectors, and the x-ray beam. Each of these three is assumed to have specific diameters instead of being considered a point or a line, Yadava says. Depending on the type of scan, the technique is better than ASIR at cutting image noise, and thus the x-rays can be even less intense. The researchers got high-quality abdomen scans of a human model using an eighth of the radiation dose of a conventional scan."

"For every list of integers x_1, ..., x_m there is some j such that x_1 + ... + x_j - x_{j+1} - ... - x_m \approx 0. So the list can be nearly balanced and for this we only need one alternation between addition and subtraction. But what if the x_i are k-dimensional integer vectors? Using results from topological degree theory we show that balancing is still possible, now with k alternations.
This result is useful in multi-objective optimization, as it allows a polynomial-time computable balance of two alternatives with conflicting costs. The application to two multi-objective optimization problems yields the following results:
- A randomized 1/2-approximation for multi-objective maximum asymmetric traveling salesman, which improves and simplifies the best known approximation for this problem.
- A deterministic 1/2-approximation for multi-objective maximum weighted satisfiability."

"The efficiency of a simple model of crossflow fan is maximized when the geometry depends on a design parameter. The flow field is numerically computed using a Galerkin method for solving a Poisson partial differential equation."

"A single target is hidden at a location chosen from a predetermined probability distribution. Then, a searcher must find a second probability distribution from which random search points are sampled such that the target is found in the minimum number of trials. Here it will be shown that if the searcher must get very close to the target to find it, then the best search distribution is proportional to the square root of the target distribution…"

"We study the problem of scheduling periodic real-time tasks so as to meet their individual minimum reward requirements. A task generates jobs that can be given arbitrary service times before their deadlines. A task then obtains rewards based on the service times received by its jobs. We show that this model is compatible to the imprecise computation models and the increasing reward with increasing service models. In contrast to previous work on these models, which mainly focus on maximize the total reward in the system, we aim to fulfill different reward requirements by different tasks, which offers better fairness and allows fine-grained tradeoff between tasks. We first derive a necessary and sufficient condition for a system, along with reward requirements of tasks, to be feasible. We also obtain an off-line feasibility optimal scheduling policy.…"

"… The aim is to find efficient decompositions that simultaneously minimize the irradiation time, the cardinality of the decomposition and the setup-time to configure the multi-leaf collimator at each step of the decomposition. We propose for this NP-hard multiobjective combinatorial problem a heuristic, based on the adaptation of the two-phase Pareto local search. Experiments are carried out on different size instances and the results are reported."

"The knapsack problem (KP) and its multidimensional version (MKP) are basic problems in combinatorial optimization. In this paper we consider their multiobjective extension (MOKP and MOMKP), for which the aim is to obtain or to approximate the set of efficient solutions. In a first step, we classify and describe briefly the existing works, that are essentially based on the use of metaheuristics. In a second step, we propose the adaptation of the two-phase Pareto local search (2PPLS) to the resolution of the MOMKP. With this aim, we use a very-large scale neighborhood (VLSN) in the second phase of the method, that is the Pareto local search. We compare our results to state-of-the-art results and we show that we obtain results never reached before by heuristics, for the biobjective instances. Finally we consider the extension to three-objective instances."

"The well known algorithm of VOLKER STRASSEN for matrix multiplication can only be used for $(m2^k \times m2^k)$ matrices. For arbitrary $(n \times n)$ matrices one has to add zero rows and columns to the given matrices to use STRASSEN's algorithm. … The aim of this work is to give a detailed analysis of the number of additional zero rows and columns and the additional work caused by STRASSEN's bad parameters. STRASSEN used the parameters $m$ and $k$ to show that his matrix multiplication algorithm needs less than $4.7n^{\log_2 7}$ flops. We can show in this paper, that these parameters cause an additional work of approx. 20 % in the worst case in comparison to the optimal strategy for the worst case. This is the main reason for the search for better parameters."

"The Lin-Kernighan heuristic is known to be one of the most successful heuristics for the Traveling Salesman Problem (TSP). It has also proven its efficiency in application to some other problems. In this paper we discuss possible adaptations of TSP heuristics for the Generalized Traveling Salesman Problem (GTSP) and focus on the case of the Lin-Kernighan algorithm. At first, we provide an easy-to-understand description of the original Lin-Kernighan heuristic. Then we propose several adaptations, both trivial and complicated. Finally, we conduct a fair competition between all the variations of the Lin-Kernighan adaptation and some other GTSP heuristics. It appears that our adaptation of the Lin-Kernighan algorithm for the GTSP reproduces the success of the original heuristic. Different variations of our adaptation outperform all other heuristics in a wide range of trade-offs between solution quality and running time, making Lin-Kernighan the state-of-the-art GTSP local search."

"In this work, we study the target detection and tracking problem in mobile sensor networks, where the performance metrics of interest are probability of detection and tracking coverage, when the target can be stationary or mobile and its duration is finite. We propose a physical coverage-based mobility model, where the mobile sensor nodes move such that the overlap between the covered areas by different mobile nodes is small. It is shown that for stationary target scenario the proposed mobility model can achieve a desired detection probability with a significantly lower number of mobile nodes especially when the detection requirements are highly stringent. Similarly, when the target is mobile the coverage-based mobility model produces a consistently higher detection probability compared to other models under investigation."

"A widely used tool in the study of risk, insurance and extreme values is the mean excess plot. One use is for validating a generalized Pareto model for the excess distribution. This paper investigates some theoretical and practical aspects of the use of the mean excess plot."

"The beam-splitting method for fine-heterogeneity cor- rection will inevitably multiply beams to transport and thus will slow down dose calculation. With the GDS al- gorithm, the dose convolution is made only once after all the beams have been transported, which minimizes the impact of the beam multiplication on computing time. In fact, for the beams individually split into several tens, the calculation time increased only by several times with the GDS. This algorithmic framework will thus enable fast and accurate treatment planning of heavy charged particle ra- diotherapy in the presence of density heterogeneity finer than the size of intrinsic beam blurring."

"The rigorous theoretical analyses of algorithms for #SAT have been proposed in the literature. As we know, previous algorithms for solving #SAT have been analyzed only regarding the number of variables as the parameter. However, the time complexity for solving #SAT instances depends not only on the number of variables, but also on the number of clauses. Therefore, it is significant to exploit the time complexity from the other point of view, i.e. the number of clauses. In this paper, we present algorithms for solving #2-SAT and #3-SAT with rigorous complexity analyses using the number of clauses as the parameter. By analyzing the algorithms, we obtain the new worst-case upper bounds O(1.1892m) for #2-SAT and O(1.4142m) for #3-SAT, where m is the number of clauses."

"In this paper, we consider the problem of blocking malicious traffic on the Internet, via source-based filtering. In particular, we consider filtering via access control lists (ACLs): these are already available at the routers today but are a scarce resource because they are stored in the expensive ternary content addressable memory (TCAM). Aggregation (by filtering source prefixes instead of individual IP addresses) helps reduce the number of filters, but comes also at the cost of blocking legitimate traffic originating from the filtered prefixes. We show how to optimally choose which source prefixes to filter, for a variety of realistic attack scenarios and operators' policies. In each scenario, we design optimal, yet computationally efficient, algorithms. Using logs from Dshield.org, we evaluate the algorithms and demonstrate that they bring significant benefit in practice."

"A new algorithm for reconstructing a two dimensional object from a set of one dimensional projected views is presented that is both computationally exact and experimentally practical. The algorithm has a computational complexity of O(n log2 n) with n = N^2 for an NxN image, is robust in the presence of noise and produces no artefacts in the reconstruction process, as is the case with conventional tomographic methods. The reconstruction process is approximation free because the object is assumed to be discrete and utilizes fully discrete Radon transforms. Noise in the projection data can be suppressed further by introducing redundancy in the reconstruction. The number of projections required for exact reconstruction and the response to noise can be controlled without comprising the digital nature of the algorithm.…"

"This paper presents the design and analysis of parallel approximation algorithms for facility-location problems, including $\NC$ and $\RNC$ algorithms for (metric) facility location, $k$-center, $k$-median, and $k$-means. These problems have received considerable attention during the past decades from the approximation algorithms community, concentrating primarily on improving the approximation guarantees. In this paper, we ask, is it possible to parallelize some of the beautiful results from the sequential setting?"

"We overview our recently introduced theory of n-fold integer programming which enables the polynomial time solution of fundamental linear and nonlinear integer programming problems in variable dimension. We demonstrate its power by obtaining the first polynomial time algorithms in several application areas including multicommodity flows and privacy in statistical databases."

"The goal of topology optimization is to find optimal material distribution in the given design domain subject to some constraints governed by certain physical properties and/or some other practical constraints during the design. In the past two decades, advances in the theory of homogenization, optimization, numerical analysis as well as newly developed engineering approaches make topology opti- mization techniques to become a standard tool of engineering design, in particular in the field of structural mechanics."

"We introduce several generalizations of classical computer science problems obtained by replacing simpler objective functions with general submodular functions. The new problems include submodular load balancing, which generalizes load balancing or minimum-makespan scheduling, submodular sparsest cut and submodular balanced cut, which generalize their respective graph cut problems, as well as submodular function minimization with a cardinality lower bound.…"

"[Open Questions] Most of the encoding schemes considered in this paper use randomness and therefore are not given explicitly. As a result, the encoding and decoding schemes are not efficient. Finding explicit and efficient encoding and decoding schemes for the scenarios described in the paper remains open."

"… The results imply that several families of constraint satisfaction problems exhibit a complexity dichotomy: the problems are in P or NP-hard, depending on the choice of the allowed relations. As concrete examples, we investigate fundamental algebraic constraint satisfaction problems. The first class consists of all first-order expansions of (Q;+). The second class is the affine variant of the first class. In both cases, we obtain full dichotomies by utilising our general methods."

"… The present work introduces new heuristic segmentation algorithms for the following optimization problem: Find a segmentation of an approximated matrix using only allowed fields and minimize the approximation error. Finally, the decomposition algorithms were implemented into an optimization programme in order to examine the assumptions of the algorithms for a clinical example. As a result, identical dose distributions with much fewer segments and a significantly smaller number of monitor units could be achieved using dosimetric constraints. Consequently, the dose delivery is more efficient and less time consuming."

"During the last decade, incremental sampling-based motion planning algorithms, such as the Rapidly-exploring Random Trees (RRTs) have been shown to work well in practice and to possess theoretical guarantees such as probabilistic completeness. However, no theoretical bounds on the quality of the solution obtained by these algorithms have been established so far. The first contribution of this paper is a negative result: it is proven that, under mild technical conditions, the cost of the best path in the RRT converges almost surely to a non-optimal value. Second, a new algorithm is considered, called the Rapidly-exploring Random Graph (RRG), and it is shown that the cost of the best path in the RRG converges to the optimum almost surely. Third, a tree version of RRG is introduced, called the RRT$^*$ algorithm, which preserves the asymptotic optimality of RRG while maintaining a tree structure like RRT.…"

"Every human likes choices. But today's fast route planning algorithms usually compute just a single route between source and target. There are beginnings to compute alternative routes, but this topic has not been studied thoroughly. Often, the aspect of meaningful alternative routes is neglected from a human point of view. We fill in this gap by suggesting mathematical definitions for such routes. As a second contribution we propose heuristics to compute them, as this is NP-hard in general."

"This page contains links to some of the most useful free software and open-source software for operations research and industrial engineering."

"It seems most people on that flight were aware of the $20 charge; overhead compartments were filled up completely, mostly with “carry-on” bags significantly larger than the one piece of luggage we had checked. As a result, a number of people had to check bags at the gate. Now here is the interesting thing… because so many people had to check bags at the gate, and those bags had to be available upon deplaning, none of us were allowed to exit the aircraft until after the bags that had been gate checked were brought up. Because so many people were trying to avoid a) waiting at the baggage carousel and b) paying twenty bucks for a piece of luggage, everyone had to wait longer. Perverse incentives lead to undesirable outcomes."

"The traffic signals didn’t stop working. They continued, but they no longer changed the time spent “green” in each direction based on time, and they no longer coordinated their “green” cycles along the main corridors:..."

"Zimpl is a little language to translate the mathematical model of a problem into a linear or (mixed-) integer mathematical program expressed in .lp or .mps file format which can be read and (hopefully) solved by a LP or MIP solver."

"Consider the following optimization problem: we are given n jobs, a time horizon T, and one machine M with processing capacity Cap >= 2. Each job has a processing time (pj), release date (rj), due date (dj), machine utilization (cj), and weight (wj). We would like to schedule all the jobs on machine M while making sure that: (i) all jobs obey their execution window [rj,dj] (to a certain extent; see possible objectives), and (ii) we respect the machine capacity at all times (i.e., given a time 0 <= t <= T, the sum of cj over all jobs running at time t is always less than or equal to Cap). Possible objective functions are: minimize makespan, minimize total (weighted) tardiness, minimize total number of late jobs, minimize total (weighted) delay, etc."

"The Computational Infrastructure for Operations Research (COIN-OR**, or simply COIN) project is an initiative to spur the development of open-source software for the operations research community."