CiteULike: AbnerCYH's optimization

A General Approximation Technique for Constrained Forest Problems

Michel Goemans — 2008-07-25T17:38:42-00:00

SIAM Journal on Computing, Vol. 24, No. 2. (1995), pp. 296-317.

Market Equilibrium via a Primal-Dual-Type Algorithm

Nikhil Devanur — 2008-07-24T04:40:27-00:00

(2002), pp. 389-395.

Fast monte-carlo algorithms for finding low-rank approximations

Alan Frieze — 2008-07-06T18:23:24-00:00

J. ACM, Vol. 51, No. 6. (November 2004), pp. 1025-1041.

Integer and fractional packings of hypergraphs

V Rödl — 2008-07-06T18:22:10-00:00

Journal of Combinatorial Theory, Series B, Vol. 97, No. 2. (March 2007), pp. 245-268.

Let F0 be a fixed k-uniform hypergraph. The problem of finding the integer F0-packing number of a k-uniform hypergraph is an NP-hard problem. Finding the fractional F0-packing number however can be done in polynomial time. In this paper we give a lower bound for the integer F0-packing number in terms of and show that .

Approximation schemes for a class of subset selection problems

Kirk Pruhs — 2008-07-01T18:36:10-00:00

Theoretical Computer Science, Vol. 382, No. 2. (31 August 2007), pp. 151-156.

In this paper we develop an easily applicable algorithmic technique/tool for developing approximation schemes for certain types of combinatorial optimization problems. Special cases that are covered by our result show up in many places in the literature. For every such special case, a particular rounding trick has been implemented in a slightly different way, with slightly different arguments, and with slightly different worst case estimations. Usually, the rounding procedure depended on certain upper or lower bounds on the optimal objective value that have to be justified in a separate argument. Our easily applied result unifies many of these results, and sometimes it even leads to a simpler proof. We demonstrate how our result can be easily applied to a broad family of combinatorial optimization problems. As a special case, we derive the existence of an FPTAS for the scheduling problem of minimizing the weighted number of late jobs under release dates and preemption on a single machine. The approximability status of this problem has been open for some time.

Boosting Support Vector Machines for Imbalanced Data Sets

Benjamin Wang — 2008-06-30T16:54:01-00:00

Foundations of Intelligent Systems (2008), pp. 38-47.

Real world data mining applications must address the issue of learning from imbalanced data sets. The problem occurs when the number of instances in one class greatly outnumbers the number of instances in the other class. Such data sets often cause a default classifier to be built due to skewed vector spaces or lack of information. Common approaches for dealing with the class imbalance problem involve modifying the data distribution or modifying the classifier. In this work, we choose to use a combination of both approaches. We use support vector machines with soft margins as the base classifier to solve the skewed vector spaces problem. Then we use a boosting algorithm to get an ensemble classifier that has lower error than a single classifier. We found that this ensemble of SVMs makes an impressive improvement in prediction performance, not only for the majority class, but also for the minority class.

Constructing boosting algorithms from SVMs: an application to one-class classification

G Ratsch — 2008-05-10T07:08:19-00:00

Pattern Analysis and Machine Intelligence, IEEE Transactions on, Vol. 24, No. 9. (September 2002), pp. 1184-1199.

We show via an equivalence of mathematical programs that a support vector (SV) algorithm can be translated into an equivalent boosting-like algorithm and vice versa. We exemplify this translation procedure for a new algorithm—one-class leveraging—starting from the one-class support vector machine (1-SVM). This is a first step toward unsupervised learning in a boosting framework. Building on so-called barrier methods known from the theory of constrained optimization, it returns a function, written as a convex combination of base hypotheses, that characterizes whether a given test point is likely to have been generated from the distribution underlying the training data. Simulations on one-class classification problems demonstrate the usefulness of our approach.

The support vector machine under test

David Meyer — 2008-05-09T19:40:26-00:00

Neurocomputing, Vol. 55, No. 1-2. (September 2003), pp. 169-186.

Support vector machines (SVMs) are rarely benchmarked against other classification or regression methods. We compare a popular SVM implementation (libsvm) to 16 classification methods and 9 regression methods--all accessible through the software --by the means of standard performance measures (classification error and mean squared error) which are also analyzed by the means of bias-variance decompositions. SVMs showed mostly good performances both on classification and regression tasks, but other methods proved to be very competitive.

A Short Algebraic Proof of the Farkas Lemma

David Bartl — 2008-04-23T05:08:39-00:00

SIAM Journal on Optimization, Vol. 19, No. 1. (2008), pp. 234-239.

The purpose of this paper is to present a generalization of the Farkas lemma with a short algebraic proof. The generalization lies in the fact that we formulate the Farkas lemma in the setting of two vector spaces over a common linearly ordered field where one of the vector spaces is also linearly ordered. At the end of the paper, we mention the key theorem and two theorems of the alternative, namely Motzkin's theorem and Tucker's theorem.

Understanding and Using Linear Programming (Universitext)

Jirí Matousek — 2008-04-23T01:25:47-00:00

(14 November 2006)

The book is an introductory textbook mainly for students of computer science and mathematics. Our guiding phrase is "what every theoretical computer scientist should know about linear programming". A major focus is on applications of linear programming, both in practice and in theory. The book is concise, but at the same time, the main results are covered with complete proofs and in sufficient detail, ready for presentation in class. The book does not require more prerequisites than basic linear algebra, which is summarized in an appendix. One of its main goals is to help the reader to see linear programming "behind the scenes".

Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond (Adaptive Computation and Machine Learning)

Bernhard Schlkopf — 2007-12-08T16:45:46-00:00

(15 December 2001)

In the 1990s, a new type of learning algorithm was developed, based on results from statistical learning theory: the Support Vector Machine (SVM). This gave rise to a new class of theoretically elegant learning machines that use a central concept of SVMs—-kernels--for a number of learning tasks. Kernel machines provide a modular framework that can be adapted to different tasks and domains by the choice of the kernel function and the base algorithm. They are replacing neural networks in a variety of fields, including engineering, information retrieval, and bioinformatics.<br /> <br /> <i>Learning with Kernels</i> provides an introduction to SVMs and related kernel methods. Although the book begins with the basics, it also includes the latest research. It provides all of the concepts necessary to enable a reader equipped with some basic mathematical knowledge to enter the world of machine learning using theoretically well-founded yet easy-to-use kernel algorithms and to understand and apply the powerful algorithms that have been developed over the last few years.

Cones of Matrices and Set-Functions and 0–1 Optimization

Lovász — 2008-03-26T14:22:54-00:00

SIAM Journal on Optimization, Vol. 1, No. 2. (1991), pp. 166-190.

It has been recognized recently that to represent a polyhedron as the projection of a higher-dimensional, but simpler, polyhedron, is a powerful tool in polyhedral combinatorics. A general method is developed to construct higher-dimensional polyhedra (or, in some cases, convex sets) whose projection approximates the convex hull of 0–1 valued solutions of a system of linear inequalities. An important feature of these approximations is that one can optimize any linear objective function over them in polynomial time.In the special case of the vertex packing polytope, a sequence of systems of inequalities is obtained such that the first system already includes clique, odd hole, odd antihole, wheel, and orthogonality constraints. In particular, for perfect (and many other) graphs, this first system gives the vertex packing polytope. For various classes of graphs, including $t$-perfect graphs, it follows that the stable set polytope is the projection of a polytope with a polynomial number of facets.An extension of the method is also discussed which establishes a connection with certain submodular functions and the Möbius function of a lattice.

Domination, Fractional Domination, 2-Packing, and Graph Products

David Fisher — 2007-02-18T23:54:52-00:00

SIAM Journal on Discrete Mathematics, Vol. 7, No. 3. (1994), pp. 493-498.

Succinct approximate convex pareto curves

Ilias Diakonikolas — 2008-03-19T08:12:31-00:00

(2008), pp. 74-83.

Some Inverse Traveling Salesman Problems

Yerim Chung — 2008-03-10T13:41:46-00:00

Electronic Notes in Discrete Mathematics, Vol. 30 (20 February 2008), pp. 9-14.

Usual inverse combinatorial optimization problems consist in modifying as little as possible the instance parameters to make a given solution optimal. In this paper we consider several extensions taking into account constraints on the weight system and inverse problems against a specific algorithm. We consider TSP under this point of view and devise both complexity and approximation results.

The Hungarian method for the assignment problem

HW Kuhn — 2007-12-20T05:05:20-00:00

Naval Research Logistics Quarterly, Vol. 2, No. 1-2. (1955), pp. 83-97.

Assuming that numerical scores are available for the performance of each of n persons on each of n jobs, the "assignment problem" is the quest for an assignment of persons to jobs so that the sum of the n scores so obtained is as large as possible. It is shown that ideas latent in the work of two Hungarian mathematicians may be exploited to yield a new method of solving this problem.

On Two Techniques of Combining Branching and Treewidth

Fedor Fomin — 2007-12-19T05:33:25-00:00

Algorithmica

Abstract Branch & Reduce and dynamic programming on graphs of bounded treewidth are among the most common and powerful techniques used in the design of moderately exponential time exact algorithms for NP hard problems. In this paper we discuss the efficiency of simple algorithms based on combinations of these techniques. The idea behind these algorithms is very natural: If a parameter like the treewidth of a graph is small, algorithms based on dynamic programming perform well. On the other side, if the treewidth is large, then there must be vertices of high degree in the graph, which is good for branching algorithms. We give several examples of possible combinations of branching and programming which provide the fastest known algorithms for a number of NP hard problems. All our algorithms require non-trivial balancing of these two techniques. In the first approach the algorithm either performs fast branching, or if there is an obstacle for fast branching, this obstacle is used for the construction of a path decomposition of small width for the original graph. Using this approach we give the fastest known algorithms for Minimum Maximal Matching and for counting all 3-colorings of a graph. In the second approach the branching occurs until the algorithm reaches a subproblem with a small number of edges (and here the right choice of the size of subproblems is crucial) and then dynamic programming is applied on these subproblems of small width. We exemplify this approach by giving the fastest known algorithm to count all minimum weighted dominating sets of a graph. We also discuss how similar techniques can be used to design faster parameterized algorithms.

On the History of Combinatorial Optimization (till 1960)

Alexander Schrijver — 2007-08-16T21:55:25-00:00

(2005), pp. 1-68.

Algorithmic aspects of the substitution decomposition in optimization over relations, set systems and Boolean functions

RH Möhring — 2007-12-04T10:30:47-00:00

Annals of Operations Research, Vol. 4, No. 1. (1 December 1985), pp. 195-225.

In the last years, decomposition techniques have seen an increasing application to the solution of problems from operations research and combinatorial optimization, in particular in network theory and graph theory. This paper gives a broad treatment of a particular aspect of this approach, viz. the design of algorithms to compute the decomposition possibilities for a large class of discrete structures. The decomposition considered is thesubstitution decomposition (also known as modular decomposition, disjunctive decomposition, X-join or ordinal sum). Under rather general assumptions on the type of structure considered, these (possibly exponentially many) decomposition possibilities can be appropriately represented in acomposition tree of polynomial size. The task of determining this tree is shown to be polynomially equivalent to the seemingly weaker task of determining the closed hull of a given set w.r.t. a closure operation associated with the substitution decomposition. Based on this reduction, we show that for arbitrary relations the composition tree can be constructed in polynomial time. For clutters and monotonic Boolean functions, this task of constructing the closed hull is shown to be Turing-reducible to the problem of determining the circuits of the independence system associated with the clutter or the prime implicants of the Boolean function. This leads to polynomial algorithms for special clutters or monotonic Boolean functions. However, these results seem not to be extendable to the general case, as we derive exponential lower bounds for oracle decomposition algorithms for arbitrary set systems and Boolean functions.

Models of Greedy Algorithms for Graph Problems

Sashka Davis — 2007-12-03T06:14:24-00:00

Algorithmica

Abstract Borodin et al. (Algorithmica 37(4):295–326, 2003) gave a model of greedy-like algorithms for scheduling problems and Angelopoulos and Borodin (Algorithmica 40(4):271–291, 2004) extended their work to facility location and set cover problems. We generalize their model to include other optimization problems, and apply the generalized framework to graph problems. Our goal is to define an abstract model that captures the intrinsic power and limitations of greedy algorithms for various graph optimization problems, as Borodin et al. (Algorithmica 37(4):295–326, 2003) did for scheduling. We prove bounds on the approximation ratio achievable by such algorithms for basic graph problems such as shortest path, weighted vertex cover, Steiner tree, and independent set. For example, we show that, for the shortest path problem, no algorithm in the FIXED priority model can achieve any approximation ratio (even one dependent on the graph size), but the well-known Dijkstra’s algorithm is an optimal ADAPTIVE priority algorithm. We also prove that the approximation ratio for weighted vertex cover achievable by ADAPTIVE priority algorithms is exactly 2. Here, a new lower bound matches the known upper bounds (Johnson in J. Comput. Syst. Sci. 9(3):256–278, 1974). We give a number of other lower bounds for priority algorithms, as well as a new approximation algorithm for minimum Steiner tree problem with weights in the interval [1,2].

Greedoids (Algorithms and Combinatorics)

BH Korte — 2005-12-01T14:50:38-00:00

(22 October 1991)

With the advent of computers, algorithmic principles play an ever increasing role in mathematics. Algorithms have to exploit the structure of the underlying mathematical object; and properties exploited by algorithms are often closely tied to classical structural analysis in mathematics. This connection between algorithms and structure is in particular apparent in discrete mathematics, where proofs are often constructive, and can be turned into algorithms more directly. The principle of greediness plays a fundamental role both in the design of continuous algorithms (where it is called the steepest descent or gradient method) and of discrete algorithms. The discrete structure most closely related to greediness is a matroid; in fact, matroids may be characterized axiomatically as those independence systems for which the greedy solution is optimal for certain optimization problems (e.g. linear objective functions, bottleneck functions). This book is an attempt to unify different approaches and to lead the reader from fundamental results in matroid theory to the current borderline of open research problems. The monograph begins by reviewing classical concepts from matroid theroy and extending them to greedoids. It then proceeds to the discussion of subclasses like interval greedoids, antimatroids or convex geometries, greedoids on partically ordered sets and greedoid intersections. Emphasis is placed on optimization problems in greedois. An algorithmic characterization of greedoids in terms of the greedy algorithm is derived, the behaviour with respect to linear functions is investigated, the shortest path problem for graphs is extended to a class of greedoids, linear descriptions of antimatroid polyhedra and complexity results are given and the Rado-Hall theorem on transversals is generalized. The self-contained volume which assumes only a basic familarity with combinatorial optimization ends with a chapter on topological results in connection with greedoids.

On Fixed-Parameter Tractability and Approximability of NP Optimization Problems

Liming Cai — 2007-11-15T09:24:36-00:00

Journal of Computer and System Sciences, Vol. 54, No. 3. (June 1997), pp. 465-474.

Fixed-parameter tractability of NP optimization problems is studied by relating it to approximability of the problems. It is shown that an NP optimization problem is fixed-parameter tractable if it admits a fully polynomial-time approximation scheme, or if it belongs to the class MAX SNP or to the class MIN F+[Pi]1. This provides strong evidence that noW[1]-hard NP optimization problems belong to these optimization classes and includes a very large class of approximable optimization problems into the class of fixed-parameter tractable problems. Evidence is also demonstrated to support the current working hypothesis in the theory of fixed-parameter tractability.

Parameterized complexity and polynomial-time approximation schemes

Xiuzhen Huang — 2007-11-13T10:33:37-00:00

(December 2004)

According to the theory of NPcompleteness, many problems that have important realworld applications are NPhard. This excludes the possibility of solving them in polynomial time unless P=NP. A number of approaches have been proposed in dealing with NPhard problems, among them are approximation algorithms and parameterized algorithms. The study of approximation algorithms tries to ﬁnd good enough solutions instead of optimal solutions in polynomial time, while parameterized algorithms try to give exact solutions when a natural parameter is small. In this thesis, we study the structural properties of parameterized computation and approximation algorithms for NP optimization problems. In particular, we investigate the relationship between parameterized complexity and polynomialtime approximation scheme (PTAS) for NP optimization problems. We give nice characterizations for two important subclasses in PTAS: Fully Polynomial Time Approximation Scheme (FPTAS) and Effcient Polynomial Time Approximation Scheme (EPTAS), using the theory of parameterized complexity. Our characterization of the class FPTAS has its advantages over the former characterizations, and our characterization of EPTAS is the ﬁrst systematic investigation of this new but important approximation class. We develop new techniques to derive strong computational lower bounds for certain parameterized problems based on the theory of parameterized complexity. For example, we prove that unless an unlikely collapse occurs in parameterized complexity theory, the clique problem could not be solved in time O(f (k)no(k)) for any function f . This lower bound matches the upper bound of the trivial algorithm that simply enumerates and checks all subsets of k vertices in the given graph of n vertices. We then extend our techniques to derive computational lower bounds for PTAS and EPTAS algorithms of NP optimization problems. We prove that certain NP optimization problems with known PTAS algorithms have no PTAS algorithms of running time O(f (1/Epsilon)no(1/Epsilon)) for any function f . Therefore, for these NP optimization problems, although theoretically they can be approximated in polynomial time to an arbitrarily small error bound Epsilon, they have no practically effective approximation algorithms for small error bound Epsilon. To our knowledge, this is the ﬁrst time such lower bound results have been derived for PTAS algorithms. This seems to open a new direction for the study of computational lower bounds on the approximability of NP optimization problems.

Systems of Distinct Representations and Linear Programming

AJ Hoffman — 2007-11-08T11:11:25-00:00

The American Mathematical Monthly, Vol. 63, No. 7. (1956), pp. 455-460.

Systems Analysis by Graphs and Matroids: Structural Solvability and Controllability (Algorithms and Combinatorics, Vol 3)

Kazuo Murota — 2007-10-31T16:52:10-00:00

(02 July 1987)

Recent technology involves large-scale physical or engineering systems consisting of thousands of interconnected elementary units. This monograph illustrates how engineering problems can be solved using the recent results of combinatorial mathematics through appropriate mathematical modeling. The structural solvability of a system of linear or nonlinear equations as well as the structural controllability of a linear time-invariant dynamical system are treated by means of graphs and matroids. Special emphasis is laid on the importance of relevant physical observations to successful mathematical modelings. The reader will become acquainted with the concepts of matroid theory and its corresponding matroid theoretical approach. This book is of interest to graduate students and researchers.

Linear Programming Duality: An Introduction to Oriented Matroids (Universitext)

Achim Bachem — 2007-10-31T16:48:45-00:00

(26 August 1992)

This book presents an elementary introduction to the theory of oriented matroids. The way oriented matroids are intro- duced emphasizes that they are the most general - and hence simplest - structures for which linear Programming Duality results can be stated and proved. The main theme of the book is duality. Using Farkas' Lemma as the basis the authors start withre- sults on polyhedra in Rn and show how to restate the essence of the proofs in terms of sign patterns of oriented ma- troids. Most of the standard material in Linear Programming is presented in the setting of real space as well as in the more abstract theory of oriented matroids. This approach clarifies the theory behind Linear Programming and proofs become simpler. The last part of the book deals with the facial structure of polytopes respectively their oriented matroid counterparts. It is an introduction to more advanced topics in oriented matroid theory. Each chapter contains suggestions for furt- herreading and the references provide an overview of the research in this field.

Algorithmic Game Theory

2007-10-31T16:34:54-00:00

(24 September 2007)

In the last few years game theory has had a substantial impact on computer science, especially on Internet- and e-commerce-related issues. More than 40 of the top researchers in this field have written chapters that go from the foundations to the state of the art. Basic chapters on algorithmic methods for equilibria, mechanism design and combinatorial auctions are followed by chapters on incentives and pricing, cost sharing, information markets and cryptography and security. Students, researchers and practitioners alike need to learn more about these fascinating theoretical developments and their widespread practical application.

Walrasian Equilibrium: Hardness, Approximations and Tractable Instances

Ning Chen — 2007-10-17T06:35:38-00:00

Algorithmica

Abstract We study the complexity issues for Walrasian equilibrium in a special case of combinatorial auction, called single-minded auction, in which every participant is interested in only one subset of commodities. Chen et al. (J. Comput. Syst. Sci. 69(4): 675–687, 2004) showed that it is NP-hard to decide the existence of a Walrasian equilibrium for a single-minded auction and proposed a notion of approximate Walrasian equilibrium called relaxed Walrasian equilibrium. We show that every single-minded auction has a relaxed Walrasian equilibrium that satisfies at least two-thirds of the participants, proving a conjecture posed in Chen et al. (J. Comput. Syst. Sci. 69(4): 675–687, 2004). Motivated by practical considerations, we introduce another concept of approximate Walrasian equilibrium called weak Walrasian equilibrium. We show NP-completeness and hardness of approximation results for weak Walrasian equilibria. In search of positive results, we restrict our attention to the tollbooth problem (Guruswami et al. in Proceedings of the Symposium on Discrete Algorithms (SODA), pp. 1164–1173, 2005), where every participant is interested in a single path in some underlying graph. We give a polynomial time algorithm to determine the existence of a Walrasian equilibrium and compute one (if it exists), when the graph is a tree. However, the problem is still NP-hard for general graphs.

Stochastic Order Relations and Lattices of Probability Measures

Alfred Müller — 2007-10-03T11:06:13-00:00

SIAM J. on Optimization, Vol. 16, No. 4. (2006), pp. 1024-1043.

Approximation Algorithms for Multi-Criteria Traveling Salesman Problems

Bodo Manthey — 2007-08-23T13:44:42-00:00

(9 Aug 2007)

In multi-criteria optimization problems, several objective functions have to be optimized. Since the different objective functions are usually in conflict with each other, one cannot consider only one particular solution as the optimal solution. Instead, the aim is to compute a so-called Pareto curve of solutions. Since Pareto curves cannot be computed efficiently in general, we have to be content with approximations to them. We design a deterministic polynomial-time algorithm for multi-criteria g-metric STSP that computes (min1 +g, 2g^2/(2g^2 -2g +1) + eps)-approximate Pareto curves for all 1/2<=g<=1. In particular, we obtain a (2+eps)-approximation for multi-criteria metric STSP. We also present two randomized approximation algorithms for multi-criteria g-metric STSP that achieve approximation ratios of (2g^3 +2g^2)/(3g^2 -2g +1) + eps and (1 +g)/(1 +3g -4g^2) + eps, respectively. Moreover, we present randomized approximation algorithms for multi-criteria g-metric ATSP (ratio 1/2 + g^3/(1 -3g^2) + eps) for g < 1/sqrt(3)), STSP with weights 1 and 2 (ratio 4/3) and ATSP with weights 1 and 2 (ratio 3/2). To do this, we design randomized approximation schemes for multi-criteria cycle cover and graph factor problems.

Shipper collaboration

Ozlem Ergun — 2007-08-28T01:30:06-00:00

Computers & Operations Research, Vol. 34, No. 6. (June 2007), pp. 1551-1560.

The interest in collaborative logistics is fuelled by the ever increasing pressure on companies to operate more efficiently, the realization that suppliers, consumers, and even competitors, can be potential collaborative partners in logistics, and the connectivity provided by the Internet. Logistics exchanges or collaborative logistics networks use the internet as a common computing platform to implement strategies designed to reduce "hidden costs" such as asset reposition costs. Through collaboration shippers may be able to identify and submit tours with little or no asset repositioning to a carrier, as opposed to submitting individual lanes, in return for more favorable rates. In this paper, we focus on finding a set of tours connecting regularly executed truckload shipments so as to minimize asset repositioning. Mathematically, the truckload shipper collaboration problem translates into covering a subset of arcs in a directed Euclidean graph by a minimum cost set of constrained cycles. We formulate the lane covering problem, propose several solution algorithms, and conduct a computational study on the effectiveness of these methodologies.

Nowhere zero flows in line graphs

Zhi-Hong Chen — 2007-08-27T13:46:20-00:00

Discrete Mathematics, Vol. 230, No. 1-3. (6 March 2001), pp. 133-141.

Cai an Corneil (Discrete Math. 102 (1992) 103-106), proved that if a graph has a cycle double cover, then its line graph also has a cycle double cover, and that the validity of the cycle double cover conjecture on line graphs would imply the truth of the conjecture in general. In this note we investigate the conditions under which a graph G has a nowhere zero k-flow would imply that L(G), the line graph of G, also has a nowhere zero k-flow. The validity of Tutte's flow conjectures on line graphs would also imply the truth of these conjectures in general.

Approximating Maximum Weight Cycle Covers in Directed Graphs with Weights Zero and One

Markus Bläser — 2007-08-27T13:14:58-00:00

Algorithmica, Vol. 42, No. 2. (1 April 2005), pp. 121-139.

A cycle cover of a graph is a spanning subgraph, each node of which is part of exactly one simple cycle. A k-cycle cover is a cycle cover where each cycle has length at least k. Given a complete directed graph with edge weights zero and one, Max-k-DDC(0,1) is the problem of finding a k-cycle cover with maximum weight. We present a 2/3 approximation algorithm for Max-k-DDC(0,1) with running time O(n 5/2). This algorithm yields a 4/3 approximation algorithm for Max-k-DDC(1,2) as well. Instances of the latter problem are complete directed graphs with edge weights one and two. The goal is to find a k-cycle cover with minimum weight. We particularly obtain a 2/3 approximation algorithm for the asymmetric maximum traveling salesman problem with distances zero and one and a 4/3 approximation algorithm for the asymmetric minimum traveling salesman problem with distances one and two. As a lower bound, we prove that Max-k-DDC(0,1) for k = 3 and Max-k-UCC(0,1) (finding maximum weight cycle covers in undirected graphs) for k = 7 are \APX-complete.

Optimal spaced seeds for faster approximate string matching

Martin Farach-Colton — 2007-08-03T16:57:32-00:00

Journal of Computer and System Sciences, Vol. 73, No. 7. (November 2007), pp. 1035-1044.

Filtering is a standard technique for fast approximate string matching in practice. In filtering, a quick first step is used to rule out almost all positions of a text as possible starting positions for a pattern. Typically this step consists of finding the exact matches of small parts of the pattern. In the followup step, a slow method is used to verify or eliminate each remaining position. The running time of such a method depends largely on the quality of the filtering step, as measured by its false positives rate. The quality of such a method depends on the number of true matches that it misses, that is, on its false negative rate. A spaced seed is a recently introduced type of filter pattern that allows gaps (i.e. do not cares) in the small sub-pattern to be searched for. Spaced seeds promise to yield a much lower false positives rate, and thus have been extensively studied, though heretofore only heuristically or statistically. In this paper, we show how to design almost optimal spaced seeds that yield no false negatives.

Partitions: Optimality and Clustering (Series on Applied Mathematics)

Frank Hwang — 2007-08-02T08:07:57-00:00

(30 November 2007)

Randomized rounding without solving the linear program

Neal Young — 2007-03-27T11:08:02-00:00

(1995), pp. 170-178.

Simple image set of linear mappings in a max-min algebra

Martin Gavalec — 2007-03-27T10:53:05-00:00

Discrete Applied Mathematics, Vol. 155, No. 5. (15 March 2007), pp. 611-622.

For a given linear mapping, determined by a square matrix A in a max-min algebra, the set SA consisting of all vectors with a unique pre-image (in short: the simple image set of A) is considered. It is shown that if the matrix A is generally trapezoidal, then the closure of SA is a subset of the set of all eigenvectors of A. In the general case, there is a permutation [pi], such that the closure of SA is a subset of the set of all eigenvectors permuted by [pi]. The simple image set of the matrix square and the topological aspects of the problem are also described.

An approximation scheme for stochastic linear programming and its application to stochastic integer programs

David Shmoys — 2007-03-27T10:33:05-00:00

J. ACM, Vol. 53, No. 6. (November 2006), pp. 978-1012.

An Algebraic Perspective of Group Relaxations

Rekha Thomas — 2007-03-27T10:27:02-00:00

(3 Oct 2001)

This is an expository article on recent developments in the theory of group relaxations in integer programming from an algebraic perspective.

Stochastic Programming (Wiley-Interscience Series in Systems and Optimization)

Peter Kall — 2006-06-14T16:06:49-00:00

(05 August 1994)

Carefully written to cover all necessary background material from both linear and non-linear programming as well as probability theory, the book brings together the methods and techniques previously described in disparate sources. Topics include decision trees and dynamic programming, recourse problems, probabilistic constraints, preprocessing and network problems. Emphasises the appropriate use of the techniques described. Exercises are provided at the end of each chapter.