Journal: Discrete Optimization

Found 150 papers in total
The k-path tree matroid and its applications to survivable network design
The k-path tree matroid and its applications to survivable network design
2008,
We define the k -path tree matroid, and use it to solve network design problems in...
The Grothendieck constant of random and pseudo-random graphs
The Grothendieck constant of random and pseudo-random graphs
2008,
The Grothendieck constant of a graph G=(V,E) is the least constant K such that for...
A branch-and-cut approach to the crossing number problem
A branch-and-cut approach to the crossing number problem
2008,
The crossing number of a graph is the minimum number of edge crossings in any drawing...
An improved algorithm for computing Steiner minimal trees in Euclidean d-space
An improved algorithm for computing Steiner minimal trees in Euclidean d-space
2008,
We describe improvements to Smith's branch-and-bound (B&B) algorithm for the...
Partition inequalities for capacitated survivable network design based on directed p-cycles
Partition inequalities for capacitated survivable network design based on directed p-cycles
2008,
We study the design of capacitated survivable networks using directed p-cycles. A...
A pricing problem under Monge property
A pricing problem under Monge property
2008,
We study a pricing problem where buyers with non-uniform demand purchase one of many...
George Dantzig's contributions to integer programming
George Dantzig's contributions to integer programming
2008,
This paper reviews George Dantzig's contributions to integer programming, especially...
An algorithmic framework for convex mixed integer nonlinear programs
An algorithmic framework for convex mixed integer nonlinear programs
2008,
This paper is motivated by the fact that mixed integer nonlinear programming is an...
N-fold integer programming
N-fold integer programming
2008,
In this article we study a broad class of integer programming problems in variable...
Simultaneously lifting sets of binary variables into cover inequalities for knapsack polytopes
Simultaneously lifting sets of binary variables into cover inequalities for knapsack polytopes
2008,
Cover inequalities are commonly used cutting planes for the 0–1 knapsack...
George Dantzig in the development of economic analysis
George Dantzig in the development of economic analysis
2008,
The role of optimization is central to economic analysis, particularly in its...
A unified interpretation of several combinatorial dualities
A unified interpretation of several combinatorial dualities
2008,
Several combinatorial structures exhibit a duality relation that yields interesting...
ϵ-optimization schemes and L-bit precision: Alternative perspectives for solving combinatorial optimization problems
ϵ-optimization schemes and L-bit precision: Alternative perspectives for solving combinatorial optimization problems
2008,
Motivated by the need to deal with imprecise data in real-world optimization problems,...
George Dantzig's impact on the theory of computation
George Dantzig's impact on the theory of computation
2008,
George Dantzig created the simplex algorithm for linear programming, perhaps the most...
Fair cost allocations under conflicts: a game-theoretic point of view
Fair cost allocations under conflicts: a game-theoretic point of view
2008,
Optimization theory resolves problems to minimize total costs when the agents are...
Complexity of the min–max (regret) versions of min cut problems
Complexity of the min–max (regret) versions of min cut problems
2008,
This paper investigates the complexity of the min–max and min–max regret...
Strong valid inequalities for the resource-constrained scheduling problem with uniform resource requirements
Strong valid inequalities for the resource-constrained scheduling problem with uniform resource requirements
2008,
We consider the resource-constrained scheduling problem when each job's resource...
Approximation algorithm for minimizing total latency in machine scheduling with deliveries
Approximation algorithm for minimizing total latency in machine scheduling with deliveries
2008,
We study the problem of minimizing total latency in machine scheduling with...
Solving mirrored traveling tournament problem benchmark instances with eight teams
Solving mirrored traveling tournament problem benchmark instances with eight teams
2008,
A two-phase method based on generating timetables from one-factorizations and finding...
Linear-programming design and analysis of fast algorithms for Max 2-CSP
Linear-programming design and analysis of fast algorithms for Max 2-CSP
2007,
The class Max ( r ,2)-CSP, or simply Max 2-CSP, consists of constraint satisfaction...
Approximation of the Quadratic Set Covering problem
Approximation of the Quadratic Set Covering problem
2007,
We study in this article the polynomial approximation properties of the Quadratic Set...
Online bin packing with resource augmentation
Online bin packing with resource augmentation
2007,
In competitive analysis, we usually do not put any restrictions on the computational...
A polynomial time equivalence between DNA sequencing and the exact perfect matching problem
A polynomial time equivalence between DNA sequencing and the exact perfect matching problem
2007,
We investigate the computational complexity of a combinatorial problem that arises in...
Algorithms for the bounded set-up knapsack problem
Algorithms for the bounded set-up knapsack problem
2007,
The Bounded Set-up Knapsack Problem (BSKP) is a generalization of the Bounded Knapsack...
Papers per page: