Journal: Algorithmica

Found 758 papers in total
Trade‐offs Between the Size of Advice and Broadcasting Time in Trees
Trade‐offs Between the Size of Advice and Broadcasting Time in Trees
2011,
We study the problem of the amount of information required to perform fast...
Approximating Minimum‐Power Degree and Connectivity Problems
Approximating Minimum‐Power Degree and Connectivity Problems
2011,
Power optimization is a central issue in wireless network design. Given a graph with...
Competitive Cost Sharing with Economies of Scale
Competitive Cost Sharing with Economies of Scale
2011,
We consider a general class of non‐cooperative buy‐at‐bulk cost...
Testing Convexity Properties of Tree Colorings
Testing Convexity Properties of Tree Colorings
2011,
A coloring of a graph is convex if it induces a partition of the vertices into...
Permutation Betting Markets: Singleton Betting with Extra Information
Permutation Betting Markets: Singleton Betting with Extra Information
2011,
We study permutation betting markets, introduced by Chen et al. (2007). For these...
A Stronger Model of Dynamic Programming Algorithms
A Stronger Model of Dynamic Programming Algorithms
2011,
We define a formal model of dynamic programming algorithms which we call Prioritized...
An Approximation Algorithm for the Minimum Co‐Path Set Problem
An Approximation Algorithm for the Minimum Co‐Path Set Problem
2011,
We present an approximation algorithm for the problem of finding a minimum set of...
Planar Feedback Vertex Set and Face Cover: Combinatorial Bounds and Subexponential Algorithms
Planar Feedback Vertex Set and Face Cover: Combinatorial Bounds and Subexponential Algorithms
2011,
The Planar Feedback Vertex Set problem asks whether an n ‐vertex planar graph...
Algorithms for Marketing‐Mix Optimization
Algorithms for Marketing‐Mix Optimization
2011,
Algorithms for determining quality/cost/price tradeoffs in saturated markets are...
The Directed Orienteering Problem
The Directed Orienteering Problem
2011,
This paper studies vehicle routing problems on asymmetric metrics. Our starting point...
k‐Outerplanar Graphs, Planar Duality, and Low Stretch Spanning Trees
k‐Outerplanar Graphs, Planar Duality, and Low Stretch Spanning Trees
2011,
Low distortion probabilistic embedding of graphs into approximating trees is an...
Approximability of Sparse Integer Programs
Approximability of Sparse Integer Programs
2011,
The main focus of this paper is a pair of new approximation algorithms for certain...
Maximum Flow in Directed Planar Graphs with Vertex Capacities
Maximum Flow in Directed Planar Graphs with Vertex Capacities
2011,
In this paper we present an O ( n log n ) time algorithm for finding a maximum flow in...
Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth
Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth
2011,
We consider the multivariate interlace polynomial introduced by Courcelle ( 2008),...
A Fast Output‐Sensitive Algorithm for Boolean Matrix Multiplication
A Fast Output‐Sensitive Algorithm for Boolean Matrix Multiplication
2011,
We use randomness to exploit the potential sparsity of the Boolean matrix product in...
On the Performance of Approximate Equilibria in Congestion Games
On the Performance of Approximate Equilibria in Congestion Games
2011,
We study the performance of approximate Nash equilibria for congestion games with...
Dynamic vs. Oblivious Routing in Network Design
Dynamic vs. Oblivious Routing in Network Design
2011,
Consider the robust network design problem of finding a minimum cost network with...
Improved Approximation Algorithms for Label Cover Problems
Improved Approximation Algorithms for Label Cover Problems
2011,
In this paper we consider both the maximization variant Max Rep and the minimization...
Constant‐Degree Graph Expansions that Preserve Treewidth
Constant‐Degree Graph Expansions that Preserve Treewidth
2011,
Many hard algorithmic problems dealing with graphs, circuits, formulas and constraints...
New Approximation Algorithms for Minimum Cycle Bases of Graphs
New Approximation Algorithms for Minimum Cycle Bases of Graphs
2011,
We consider the problem of computing an approximate minimum cycle basis of an...
Tight Approximation Ratio of a General Greedy Splitting Algorithm for the Minimum k‐Way Cut Problem
Tight Approximation Ratio of a General Greedy Splitting Algorithm for the Minimum k‐Way Cut Problem
2011,
For an edge‐weighted connected undirected graph, the minimum k ‐way cut...
A Unified Approach to Approximating Partial Covering Problems
A Unified Approach to Approximating Partial Covering Problems
2011,
An instance of the generalized partial cover problem consists of a ground set U and a...
Competitive Algorithms for Due Date Scheduling
Competitive Algorithms for Due Date Scheduling
2011,
We consider several online scheduling problems that arise when customers request...
On Bounded Leg Shortest Paths Problems
On Bounded Leg Shortest Paths Problems
2011,
Let V be a set of points in a d ‐dimensional l p ‐metric space. Let s ,...
Papers per page: