Scheduling Packets with Values and Deadlines in Size-Bounded Buffers
Motivated by providing quality-of-service differentiated services in the Internet, we consider buffer management algorithms for network switches. We study a multi-buffer model. A network switch consists of multiple size-bounded buffers such that at any ...
Some variations on constrained minimum enclosing circle problem
Given a set P of n points and a straight line L, we study three important variations of minimum enclosing circle problem as follows:
Complexity of determining the most vital elements for the p-median and p-center location problems
We consider the k most vital edges (nodes) and min edge (node) blocker versions of the p -median and p -center location problems. Given a weighted connected graph with distances on edges and weights on nodes, the k most vital edges (nodes) p -...
Coverage with k-transmitters in the presence of obstacles
- Brad Ballinger,
- Nadia Benbernou,
- Prosenjit Bose,
- Mirela Damian,
- Erik D. Demaine,
- Vida Dujmović,
- Robin Flatland,
- Ferran Hurtado,
- John Iacono,
- Anna Lubiw,
- Pat Morin,
- Vera Sacristán,
- Diane Souvaine,
- Ryuhei Uehara
For a fixed integer k 0, a k -transmitter is an omnidirectional wireless transmitter with an infinite broadcast range that is able to penetrate up to k "walls", represented as line segments in the plane. We develop lower and upper bounds for the ...
Approximating multilinear monomial coefficients and maximum multilinear monomials in multivariate polynomials
This paper is our third step towards developing a theory of testing monomials in multivariate polynomials and concentrates on two problems: (1) How to compute the coefficients of multilinear monomials; and (2) how to find a maximum multilinear monomial ...
Improved approximation for spanning star forest in dense graphs
A spanning subgraph of a graph G is called a spanning star forest of G if it is a collection of node-disjoint trees of depth at most 1. The size of a spanning star forest is the number of leaves in all its components. The goal of the spanning ...
A primal-dual approximation algorithm for the Asymmetric Prize-Collecting TSP
We present a primal-dual log( n ) -approximation algorithm for the version of the asymmetric prize collecting traveling salesman problem, where the objective is to find a directed tour that visits a subset of vertices such that the length of the tour ...
Preemptive scheduling on two identical parallel machines with a single transporter
We consider a scheduling problem on two identical parallel machines, in which the jobs are moved between the machines by an uncapacitated transporter. In the processing preemption is allowed. The objective is to minimize the time by which all completed ...
Discrete optimization with polynomially detectable boundaries and restricted level sets
The paper describes an optimization procedure for a class of discrete optimization problems which is defined by certain properties of the boundary of the feasible region and level sets of the objective function. It is shown that these properties are ...
A simplified algorithm for the all pairs shortest path problem with O(n2logn) expected time
The best known expected time for the all pairs shortest path problem on a directed graph with non-negative edge costs is O ( n 2log n ) by Moffat and Takaoka. Let the solution set be the set of vertices to which the given algorithm has so far ...