Risk-bounded motion planning in dynamic environments for autonomous driving presents complex challenges, particularly in solving the nonconvex problem of ensuring continuous, safe, and real-time navigation towards a destination. This paper introduces an online graph-based local planning approach constrained by a user-defined driving style in terms of a risk budget$\Delta$for the entire mission. Our online approach assigns a risk bound to each motion planning decision, ensuring that the total risk consumed remains within$\Delta$. First, we construct a spatial lattice graph that adheres to the vehicle's curvature constraints. Then, the trajectory planning problem is reformulated as an online optimization problem, where decisions must be made sequentially without prior knowledge of future events. Therefore, we propose a reduction to the problem to be online multiple-choice knapsack problem (ON-MCKP), where the knapsack items are candidate paths generated by solving constrained shortest-path problems. To solve the ON-MCKP, we deploy online algorithms that offer theoretical guarantees on the risk allocation throughout the entire mission. The effectiveness of our method is demonstrated empirically, showing significant improvements in the objective without violating safety constraints.

In the monotone integer dualization problem, we are given two sets of vectors in an integer box such that no vector in the first set is dominated by a vector in the second. The question is to check if the two sets of vectors cover the entire integer box by upward and downward domination, respectively. It is known that the problem is (quasi-)polynomially equivalent to that of enumerating all maximal feasible solutions of a given monotone system of linear/separable/supermodular inequalities over integer vectors. The equivalence is established via showing that the dual family of minimal infeasible vectors has size bounded by a (quasi-)polynomial in the sizes of the family to be generated and the input description. Continuing in this line of work, in this paper, we consider systems of polynomial, second-order cone, and semidefinite inequalities. We give sufficient conditions under which such bounds can be established and highlight some applications.

We study the social welfare maximization problem in the high-multiplicity setting where agents and/or items are available in multiple types, provided that the numbers of types are small. We focus on the egalitarian and Nash social welfare maximization problems, and show that they are NP-hard even when the number of item types is a constant. Furthermore, we present two polynomial-time approximation schemes (PTAS), one for egalitarian social welfare with two item types, and one for Nash social welfare with any constant number of agent types. The first PTAS can be applied to the unrelated machine scheduling problem, thus partially solving an open question raised by Jansen and Maack in 2019. The second PTAS significantly improves upon the existing PTAS for identical agents.

Risk-bounded motion planning for autonomous driving in dynamic environments presents significant research challenges. Ensuring continuous navigation towards a destination while making real-time decisions is a nonconvex problem. This paper presents a graph-based local planning method constrained by user-specific driving preference, represented as a risk-bound criterion for motion planning. First, we propose a lattice graph construction method that adheres to the vehicle's curvature constraints. Then, we formulate the trajectory planning problem as an integer-linear programming task, addressed by our novel risk-bounded and prediction-aware constrained shortest path. Our solution accounts for both static and dynamic obstacles in urban settings, adhering to traffic regulations. At the core of our approach is a conservative spatiotemporal risk assessment mechanism, which evaluates collisions considering the uncertain delay from speed control of the ego vehicle and predicted trajectories of dynamic obstacles. We implemented our solution using the CARLA simulator and the ROS2 platform, within a comprehensive framework encompassing global planning, local planning, and vehicle control. The effectiveness of our approach is demonstrated through notable collision avoidance, improved path-tracking, and enhanced risk-bounded planning capabilities.

We consider a rate-splitting multiple access (RSMA)-based communication and radar coexistence (CRC) system. The proposed system allows an RSMA-based communication system to share spectrum with multiple radars. Furthermore, RSMA enables flexible and powerful interference management by splitting messages into common parts and private parts to partially decode interference and partially treat interference as noise. The RSMA-based CRC system thus significantly improves spectral efficiency and quality of service (QoS) of communication users (CUs). The communication network and the radars cause interference to each other, which reduces the signal-to-interference-plus-noise ratio (SINR) of the radars as well as the data rate of the CUs. Therefore, a major problem is to maximize the sum rate of the CUs while guaranteeing their QoS requirements of data transmissions and the SINR requirements of multiple radars. To achieve these objectives, we formulate a problem that optimizes i) the common rate allocation to the CUs, transmit power of common message and transmit power of private messages of the CUs, and ii) transmit power of the radars. We propose an additive approximation scheme (AAS) which solves the problem globally. Simulation results show the improvement of the AAS compared with the sequential quadratic programming (SQP) in terms of sum rate.

Unmanned aerial vehicles (UAVs), commonly known as drones, are being increasingly deployed throughout the globe as a means to streamline monitoring, inspection, mapping, and logistic routines. When dispatched on autonomous missions, drones require an intelligent decision-making system for trajectory planning and tour optimization. Given the limited capacity of their onboard batteries, a key design challenge is to ensure the underlying algorithms can efficiently optimize the mission objectives along with recharging operations during long-haul flights. With this in view, the present work undertakes a comprehensive study on automated tour management systems for an energy-constrained drone: (1) We construct a machine learning model that estimates the energy expenditure of typical multi-rotor drones while accounting for real-world aspects and extrinsic meteorological factors. (2) Leveraging this model, the joint program of flight mission planning and recharging optimization is formulated as a multi-criteria Asymmetric Traveling Salesman Problem (ATSP), wherein a drone seeks for the time-optimal energy-feasible tour that visits all the target sites and refuels whenever necessary. (3) We devise an efficient approximation algorithm with provable worst-case performance guarantees and implement it in a drone management system, which supports real-time flight path tracking and re- computation in dynamic environments. (4) The effectiveness and practicality of the proposed approach are validated through extensive numerical simulations as well as real-world experiments. Note to Practitioners—This study is stimulated by the need for developing pragmatic and provably efficient automated tour management systems for UAVs deployed on energy-constrained, long-distance flight missions. As such, UAVs provide a nifty platform for facilitating environmental monitoring, disaster management, transport of medical supplies, as well as expediting last-mile deliveries. However, existing path planners generally fall short of capturing several crucial aspects, such as detailed power consumption model (e.g., factoring in payload, wind speed and direction) or performance guarantees, potentially leading to underutilized or infeasible routing decisions. To address these issues, the present work proposes a theoretically-backed routing approach with a certifiable degree of optimality and develops an effective, practical power consumption evaluation model for multi-rotor UAVs, verified on multiple drone models.

Given a CNF formula Φ with clauses C1,…,Cm and variables V={x1,…,xn}, a truth assignment a:V→{0,1} of Φ leads to a clause sequence σΦ(a)=(C1(a),…,Cm(a))∈{0,1}m where Ci(a)=1 if clause Ci evaluates to 1 under assignment a, otherwise Ci(a)=0. The set of all possible clause sequences carries a lot of information on the formula, e.g. SAT, MAX-SAT and MIN-SAT can be encoded in terms of finding a clause sequence with extremal properties. We consider a problem posed at Dagstuhl Seminar 19211 “Enumeration in Data Management” (2019) about the generation of all possible clause sequences of a given CNF with bounded dimension. We prove that the problem can be solved in incremental polynomial time. We further give an algorithm with polynomial delay for the class of tractable CNF formulas. We also consider the generation of maximal and minimal clause sequences, and show that generating maximal clause sequences is NP-hard, while minimal clause sequences can be generated with polynomial delay.

We give an incremental polynomial time algorithm for enumerating the vertices of any polyhedron $P=P(A,\b1)=\{x\in \mathbb{R}^n \mid Ax\geq \b1,~x\geq \b0\}$, when $A$ is a totally unimodular matrix. Our algorithm is based on decomposing the hypergraph transversal problem for unimodular hypergraphs using Seymour's decomposition of totally unimodular matrices and may be of independent interest.

The Internet-of-Things (IoT) has engendered a new paradigm of integrated sensing and actuation systems for intelligent monitoring and control of smart homes and buildings. One viable manifestation is that of IoT-empowered smart lighting systems, which rely on the interplay between smart light bulbs (equipped with controllable LED devices and wireless connectivity) and mobile sensors (possibly embedded in users’ wearable devices such as smart watches, spectacles, and gadgets) to provide automated illuminance control functions tailored to users’ preferences (e.g., of brightness, color intensity, or color temperature). Typically, practical deployment of these systems precludes the adoption of sophisticated but costly location-aware sensors capable of accurately mapping out the details of a dynamic operational environment. Instead, cheap oblivious mobile sensors are often utilized, which are plagued with uncertainty in their relative locations to sensors and light bulbs. The imposed volatility, in turn, impedes the design of effective smart lighting systems for uncertain indoor environments with multiple sensors and light bulbs. With this in view, the present article sheds light on the adaptive control algorithms and modeling of such systems. First, a general model formulation of an oblivious multisensor illuminance control problem is proposed, yielding a robust framework agnostic to a dynamic surrounding environment and time-varying background light sources. Under this model, we devise efficient algorithms inducing continuous adaptive lighting control that minimizes energy consumption of light bulbs while meeting users’ preferences. The algorithms are then studied under extensive empirical evaluations in a proof-of-concept smart lighting testbed featuring LIFX programmable bulbs and smartphones (deployed as light sensing units). Lastly, we conclude by discussing the potential improvements in hardware development and highlighting promising directions for future work.

We consider two-player zero-sum stochastic mean payoff games with perfect information. We show that any such game, with a constant number of random positions and polynomially bounded positive transition probabilities, admits a polynomial time approximation scheme, both in the relative and absolute sense.

We consider the problem of finding a small hitting set in an infinite range space F=(Q,R) of bounded VC-dimension. We show that, under reasonably general assumptions, the infinite-dimensional convex relaxation can be solved (approximately) efficiently by multiplicative weight updates. As a consequence, we get an algorithm that finds, for any delta>0, a set of size O(s_F(z^*_F)) that hits (1-delta)-fraction of R (with respect to a given measure) in time proportional to log(1/delta), where s_F(1/epsilon) is the size of the smallest epsilon-net the range space admits, and z^*_F is the value of the fractional optimal solution. This exponentially improves upon previous results which achieve the same approximation guarantees with running time proportional to poly(1/delta). Our assumptions hold, for instance, in the case when the range space represents the visibility regions of a polygon in the plane, giving thus a deterministic polynomial-time O(log z^*_F)-approximation algorithm for guarding (1-delta)-fraction of the area of any given simple polygon, with running time proportional to polylog(1/delta).

Drive modes are driver-selectable pre-set configurations of powertrain and certain vehicle parameters. Plug-in hybrid electric vehicles typically feature the special options of drive modes that can affect the hybrid energy source management system; for example, electric vehicle mode (which draws fully on battery) and charge sustaining mode (which utilizes internal combustion engine to charge the battery while propelling the vehicle). This paper studies an optimization problem to enable the driver to select the appropriate drive modes for fuel minimization. We develop the optimization algorithms that optimize the decisions of drive modes based on trip information and, integrated with path planning to find an optimal path, considering intermediate filling and charging stations. We further provide an online algorithm that is based on the revealed trip information. We evaluate our algorithms empirically on a Chevrolet Volt, which shows significant fuel savings.

We show that list-coloring for any intersecting hypergraph of m edges on n vertices, and lists drawn from a set of size at most k, can be checked in quasi-polynomial time (mn)^{o(k^2*log(mn))}.

R. Lavi and C. Swamy (FOCS 2005 , J. ACM 58 (6), 25, 2011 ) introduced a general method for obtaining truthful-in-expectation mechanisms from linear programming based approximation algorithms. Due to the use of the Ellipsoid method, a direct implementation of the method is unlikely to be efficient in practice. We propose to use the much simpler and usually faster multiplicative weights update method instead. The simplification comes at the cost of slightly weaker approximation and truthfulness guarantees.

We consider finite Markov decision processes (MDPs) with undiscounted total effective payoff. We show that there exist uniformly optimal pure stationary strategies that can be computed by solving a polynomial number of linear programs. We apply this result to two-player zero-sum stochastic games with perfect information and undiscounted total effective payoff, and derive the existence of a saddle point in uniformly optimal pure stationary strategies.

A challenge in future smart grid is how to efficiently allocate power among customers considering inelastic demands, when the power supply is constrained by the network or generation capacities. This problem is an extension to the classical knapsack problem in a way that the item values are expressed as non-positive real or complex numbers representing power demands, rather than positive real numbers. The objective is to maximize the total utility of the customers. Recently in Chau-Elbassioni-Khonji [AAMAS 14], a PTAS was presented for the case where the maximum phase angle between any pair of power demands is φ ≤ π/2; and a bi-criteria FPTAS when π/2 <; φ ≤ π - ε, for any polynomially small ε. For 0 ≤ φ ≤ π/2, Yu and Chau [AAMAS 13] showed that unless P=NP, there is no FPTAS. In this paper, we present important hardness results that close the approximation gap. We show that unless P=NP, there is no α-approximation for π/2 <; π ≤ π - ε, where a is any number with polynomial length. Moreover, for the case when φ is arbitrarily close to π, neither a PTAS nor any bi-criteria approximation algorithm with polynomial guarantees can exist. In this paper, we also present a natural generalization to a networked setting such that each edge in the transmission network can have a capacity constraint. We show that there is no bi-criteria approximation algorithm with polynomial guarantees for this networked setting, even all power demands are real (non-complex) numbers.

The computation of transversal hypergraphs in output-polynomial time is a long standing open question. An Apriori-like level-wise approach (referred to as the HBC-algorithm or MTminer) was published in 2007 by Hébert, Bretto, and Crémilleux [A Data Mining Formalization to Improve Hypergraph Minimal Transversal Computation, Fundamenta Informaticae, 80(4), 2007, 415–433] and was experimentally demonstrated to have very good performance on hypergraphs with small transversals. In this short note extending the paper by Hagen [Lower bounds for three algorithms for transversal hypergraph generation, Discrete Applied Mathematics, 157(7), 2009, 1460–1469], we prove a superpolynomial lower bound for the HBC-algorithm. This lower bound also shows that the originally claimed upper bound on the HBC-algorithm's running time is wrong.

Maximizing data usage and minimizing privacy risk are two conflicting goals. Organizations always apply a set of transformations on their data before releasing it. While determining the best set of transformations has been the focus of extensive work in the database community, most of this work suffered from one or both of the following major problems: scalability and privacy guarantee. Differential Privacy provides a theoretical formulation for privacy that ensures that the system essentially behaves the same way regardless of whether any individual is included in the database. In this paper, we address both scalability and privacy risk of data anonymization. We propose a scalable algorithm that meets differential privacy when applying a specific random sampling. The contribution of the paper is two-fold: 1) we propose a personalized anonymization technique based on an aggregate formulation and prove that it can be implemented in polynomial time; and 2) we show that combining the proposed aggregate formulation with specific sampling gives an anonymization algorithm that satisfies differential privacy. Our results rely heavily on exploring the supermodularity properties of the risk function, which allow us to employ techniques from convex optimization. Through experimental studies we compare our proposed algorithm with other anonymization schemes in terms of both time and privacy risk.

We study the Unsplittable Flow Problem (UFP) and related variants, namely UFP with Bag Constraints and UFP with Rounds, on paths and trees. We provide improved constant factor approximation algorithms for all these problems under the no bottleneck assumption (NBA), which says that the maximum demand for any source-sink pair is at most the minimum capacity of any edge. We obtain these improved results by expressing a feasible solution to a natural LP relaxation of the UFP as a near-convex combination of feasible integral solutions.

We give a very simple approximation algorithm for the maximum asymmetric traveling salesman problem. The approximation guarantee of our algorithm is 2/3, which matches the best known approximation guarantee by Kaplan, Lewenstein, Shafrir and Sviridenko. Our algorithm is simple to analyze, and contrary to previous approaches, which need an optimal solution to a linear program, our algorithm is combinatorial and only uses maximum weight perfect matching algorithm.

We present a 4-approximation algorithm for the problem of placing the fewest guards on a 1.5D terrain so that every point of the terrain is seen by at least one guard. This improves on the previous best approximation factor of 5 (see King in Proceedings of the 13th Latin American Symposium on Theoretical Informatics, pp. 629–640, 2006 ). Unlike most of the previous techniques, our method is based on rounding the linear programming relaxation of the corresponding covering problem. Besides the simplicity of the analysis, which mainly relies on decomposing the constraint matrix of the LP into totally balanced matrices, our algorithm, unlike previous work, generalizes to the weighted and partial versions of the basic problem.

We consider the Traveling Salesman Problem with Neighborhoods (TSPN) in doubling metrics. The goal is to find a shortest tour that visits each of a collection of n subsets ( regions or neighborhoods ) in the underlying metric space. We give a quasi-polynomial time approximation scheme (QPTAS) when the regions are what we call α - fat weakly disjoint . This notion combines the existing notions of diameter variation, fatness and disjointness for geometric objects and generalizes these notions to any arbitrary metric space. Intuitively, the regions can be grouped into a bounded number of types, where in each type, the regions have similar upper bounds for their diameters, and each such region can designate a point such that these points are far away from one another. Our result generalizes the polynomial time approximation scheme (PTAS) for TSPN on the Euclidean plane by Mitchell (in SODA, pp. 11–18, 2007 ) and the QPTAS for TSP on doubling metrics by Talwar (in 36th STOC, pp. 281–290, 2004 ). We also observe that our techniques directly extend to a QPTAS for the Group Steiner Tree Problem on doubling metrics, with the same assumption on the groups.

We study the interval constrained coloring problem, a combinatorial problem arising in the interpretation of data on protein structure emanating from experiments based on hydrogen/deuterium exchange and mass spectrometry. The problem captures the challenging task of increasing the spatial resolution of experimental data in order to get a better picture of the protein structure. Since solutions proposed by any algorithmic framework have to ultimately be verified by biochemists, it is important to provide not just a single solution, but a valuable set of candidate solutions. Our contribution is a polynomial-delay polynomial-space algorithm for enumerating all exact solutions plus further approximate solutions, whose components are guaranteed to be within an absolute error of one of the optimum. Our experiments indicate that these approximate solutions are reasonably close to the optimal ones, in terms of the accumulative error. In addition, the experiments also confirm the effectiveness of the method in reducing the delay between two consecutive solutions considerably, compared to what it takes an integer programming solver to produce the next exact solution.

We consider the Traveling Salesman Problem with Neighborhoods (TSPN) in doubling metrics. The goal is to find a shortest tour that visits each of a collection of n subsets (regions or neighborhoods) in the underlying metric space. We give a QPTAS when the regions are what we call α-fat weakly disjoint. This notion combines the existing notions of diameter variation, fatness and disjointness for geometric objects and generalizes these notions to any arbitrary metric space. Intuitively the regions can be grouped into a bounded number of types, where in each type, the regions have similar upper bounds for their diameters, and each such region can designate a point such that these points are far away from one another. Our result generalizes the PTAS for TSPN on the Euclidean plane by Mitchell [27] and the QPTAS for TSP on doubling metrics by Talwar [30]. We also observe that our techniques directly extend to a QPTAS for the Group Steiner Tree Problem on doubling metrics, with the same assumption on the groups.

Given the prime conjunctive normal form (CNF) representation $\phi$ of a monotone Boolean function $f:\{0,1\}^n\to\{0,1\}$, the dualization problem calls for finding the corresponding prime disjunctive normal form representation $\psi$ of f. A very simple method works by multiplying out the clauses of $\phi$ from left to right in some order, simplifying whenever possible by using the absorption law. We show that for any monotone CNF $\phi$, left-to-right multiplication can be done in subexponential time, and for many interesting subclasses of monotone CNFs such as those with bounded size, bounded degree, bounded intersection, bounded conformality, and read-once formula, it can be done in polynomial or quasi-polynomial time.

Given a system of constraints , where ai ∊ {0, 1}n, and ℓi, ui ∊ ℝ+, for i = 1, …, m, we consider the problem Mrfs of finding the largest subsystem for which there exists a feasible solution x ≥ 0. We present approximation algorithms and inapproximability results for this problem, and study some important special cases. Our main contributions are: 1. In the general case, where ai ∊ {0, 1}n, a sharp separation in the approximability between the case when L = max{ℓ1, ⃛, ℓm} is bounded above by a polynomial in n and m, and the case when it is not. 2. In the case where A is an interval matrix, a sharp separation in approximability between the case where we allow a violation of the upper bounds by at most a (1 + ∊) factor, for any fixed ∊ > 0 and the case where no violations are allowed. Along the way, we prove that the induced matching problem on bipartite graphs is inapproximable beyond a factor of , for any ∊ > 0 unless NP=ZPP. Finally, we also show applications of Mrfs to some recently studied pricing problems.

We present a 4-approximation algorithm for the problem of placing the fewest guards on a 1.5D terrain so that every point of the terrain is seen by at least one guard. This improves on the currently best approximation factor of 5 (J. King, 2006). Unlike most of the previous techniques, our method is based on rounding the linear programming relaxation of the corresponding covering problem. Besides the simplicity of the analysis, which mainly relies on decomposing the constraint matrix of the LP into totally balanced matrices, our algorithm, unlike previous work, generalizes to the weighted and partial versions of the basic problem.

Let $\mathcal P=\mathcal P_1\times\cdots\times\mathcal P_n$ be the product of n partially ordered sets (posets). Given a subset $\mathcal A\subseteq\mathcal P$, we consider problem $\mathrm{DUAL}(\mathcal P,\mathcal A,\mathcal B)$ of extending a given partial list $\mathcal B$ of maximal independent elements of $\mathcal A$ in $\mathcal P$. We give quasi-polynomial time algorithms for solving problem $\mathrm{DUAL}(\mathcal P,\mathcal A,\mathcal B)$ when each poset $\mathcal P_i$ belongs to one of the following classes: (i) semilattices of bounded width, (ii) forests, that is, posets with acyclic underlying graphs, with either bounded in-degrees or out-degrees, or (iii) lattices defined by a set of real closed intervals.

We study the complexity of determining whether a polytope given by its vertices or facets is combinatorially isomorphic to its polar dual. We prove that this problem is Graph Isomorphism hard, and that it is Graph Isomorphism complete if and only if Vertex Enumeration is Graph Isomorphism easy. To the best of our knowledge, this is the first problem that is not equivalent to Vertex Enumeration and whose complexity status has a non-trivial impact on the complexity of Vertex Enumeration irrespective of whether checking Self-duality turns out to be strictly harder than Graph Isomorphism or equivalent to Graph Isomorphism. The constructions employed in the proof yield a class of self-dual polytopes that are interesting on their own. In particular, this class of self-dual polytopes has the property that the facet-vertex incident matrix of the polytope is transposable if and only if the matrix is symmetrizable as well. As a consequence of this construction, we also prove that checking self-duality of a polytope, given by its facet-vertex incidence matrix, is Graph Isomorphism complete, thereby answering a question of Kaibel and Schwartz.

Let G=(V,E) be an undirected graph, and let B⊆V×V be a collection of vertex pairs. We give an incremental polynomial time algorithm to generate all minimal edge sets X⊆E such that every pair (s,t)∈B of vertices is disconnected in (V,E ∖ X), generalizing well-known efficient algorithms for generating all minimal s-t cuts, for a given pair s,t of vertices. We also present an incremental polynomial time algorithm for generating all minimal subsets X⊆E such that no (s,t)∈B is a bridge in (V,X∪B). Both above problems are special cases of a more general problem that we call generating cut conjunctions for matroids: given a matroid M on ground set S=E∪B, generate all minimal subsets X⊆E such that no element b∈B is spanned by E ∖ X. Unlike the above special cases, corresponding to the cycle and cocycle matroids of the graph (V,E∪B), the more general problem of generating cut conjunctions for vectorial matroids turns out to be NP-hard.

We consider the problems of enumerating all minimal strongly connected subgraphs and all minimal dicuts of a given strongly connected directed graph G=(V,E). We show that the first of these problems can be solved in incremental polynomial time, while the second problem is NP-hard: given a collection of minimal dicuts for G, it is NP-hard to tell whether it can be extended. The latter result implies, in particular, that for a given set of points $\mathcal{A}\subseteq\mathbb{R}^{n}$ , it is NP-hard to generate all maximal subsets of $\mathcal{A}$ contained in a closed half-space through the origin. We also discuss the enumeration of all minimal subsets of $\mathcal{A}$ whose convex hull contains the origin as an interior point, and show that this problem includes as a special case the well-known hypergraph transversal problem.

We show that generating all negative cycles of a weighted graph is a hard enumeration problem, in both the directed and undirected cases. More precisely, given a family of negative (directed) cycles, it is an NP-complete problem to decide whether this family can be extended or there are no other negative (directed) cycles in the graph, implying that (directed) negative cycles cannot be generated in polynomial output time, unless P=NP. As a corollary, we solve in the negative two well-known generating problems from linear programming: (i) Given an infeasible system of linear inequalities, generating all minimal infeasible subsystems is hard. Yet, for generating maximal feasible subsystems the complexity remains open. (ii) Given a feasible system of linear inequalities, generating all vertices of the corresponding polyhedron is hard. Yet, in the case of bounded polyhedra the complexity remains open. Equiva lently, the complexity of generating vertices and extreme rays of polyhedra remains open.

Given a directed graph G=(V,A) with a non-negative weight (length) function on its arcs w:A→ℝ+ and two terminals s,t∈V, our goal is to destroy all short directed paths from s to t in G by eliminating some arcs of A. This is known as the short paths interdiction problem. We consider several versions of it, and in each case analyze two subcases: total limited interdiction, when a fixed number k of arcs can be removed, and node-wise limited interdiction, when for each node v∈V a fixed number k(v) of out-going arcs can be removed. Our results indicate that the latter subcase is always easier than the former one. In particular, we show that the short paths node-wise interdiction problem can be efficiently solved by an extension of Dijkstra’s algorithm. In contrast, the short paths total interdiction problem is known to be NP-hard. We strengthen this hardness result by deriving the following inapproximability bounds: Given k, it is NP-hard to approximate within a factor c<2 the maximum s–t distance d(s,t) obtainable by removing (at most) k arcs from G. Furthermore, given d, it is NP-hard to approximate within a factor $c<10\sqrt{5}-21\approx1.36$ the minimum number of arcs which has to be removed to guarantee d(s,t)≥d. Finally, we also show that the same inapproximability bounds hold for undirected graphs and/or node elimination.

Given a set of points P ⊆ R2, a conflict-free coloring of P w.r.t. rectangle ranges is an assignment of colors to points of P, such that each non-empty axis-parallel rectangle T in the plane contains a point whose color is distinct from all other points in P ∩ T. This notion has been the subject of recent interest, and is motivated by frequency assignment in wireless cellular networks: one naturally would like to minimize the number of frequencies (colors) assigned to bases stations (points), such that within any range (for instance, rectangle), there is no interference. We show that any set of n points in R2 can be conflict-free colored with Õ(nβ+ε) colors in expected polynomial time, for any arbitrarily small ε > 0 and β = 3?√5 2 < 0.382. This improves upon the previously known bound of O(√nlog log n/ log n).

Let M be a matroid defined by an independence oracle on ground set S, and let $A\subseteq S$. We present an incremental polynomial-time algorithm for enumerating all minimal (maximal) subsets of S which span (do not span) A. Special cases of these problems include the generation of bases, circuits, hyperplanes, flats of given rank, circuits through a given element, generalized Steiner trees, and multiway cuts in graphs, as well as some other applications. We also consider some tractable and NP-hard generation problems related to systems of polymatroid inequalities and (generalized) packing and spanning in matroids.

A new multimedia disk-scheduling algorithm, termed Cascaded-SFC, is presented. The Cascaded-SFC multimedia disk scheduler is applicable in environments where multimedia data requests arrive with different quality of service (QoS) requirements such as real-time deadline and user priority. Previous work on disk scheduling has focused on optimizing the seek times and/or meeting the real-time deadlines. The Cascaded-SFC disk scheduler provides a unified framework for multimedia disk scheduling that scales with the number of scheduling parameters. The general idea is based on modeling the multimedia disk requests as points in multiple multidimensional subspaces, where each of the dimensions represents one of the parameters (e.g., one dimension represents the request deadline, another represents the disk cylinder number, and a third dimension represents the priority of the request, etc.). Each multidimensional subspace represents a subset of the QoS parameters that share some common scheduling characteristics. Then the multimedia disk scheduling problem reduces to the problem of finding a linear order to traverse the multidimensional points in each subspace. Multiple space-filling curves are selected to fit the scheduling needs of the QoS parameters in each subspace. The orders in each subspace are integrated in a cascaded way to provide a total order for the whole space. Comprehensive experiments demonstrate the efficiency and scalability of the Cascaded-SFC disk scheduling algorithm over other disk schedulers.

We consider the problem of enumerating all minimal integer solutions of a monotone system of linear inequalities. We first show that, for any monotone system of r linear inequalities in n variables, the number of maximal infeasible integer vectors is at most rn times the number of minimal integer solutions to the system. This bound is accurate up to a polylog(r) factor and leads to a polynomial-time reduction of the enumeration problem to a natural generalization of the well-known dualization problem for hypergraphs, in which dual pairs of hypergraphs are replaced by dual collections of integer vectors in a box. We provide a quasi-polynomial algorithm for the latter dualization problem. These results imply, in particular, that the problem of incrementally generating all minimal integer solutions to a monotone system of linear inequalities can be done in quasi-polynomial time.

This paper addresses the problem of providing different levels of performance guarantee for disk I/O. In typical applications, disk requests are classified into different categories based on the required quality of service (QoS), which is usually characterized by a priority and a deadline for each request. Traditional algorithms usually service all high priority requests before low priority requests, and this may result in potential starvation for the low priority requests. In this paper, a disk-scheduling algorithm is introduced to provide such QoS guarantee and avoid starvation. Our target applications for this algorithm are non-linear editing systems for continuous data, where the block size is large enough to ignore the seek time. The proposed algorithm tries to service a request with lower priority and strict deadline only if servicing this request will not violate the deadline constraints of a higher priority request. Simulation experiments are presented to show the superiority of the proposed algorithm over the traditional ones.