Search results for "NP-hard"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
11	Lili Tan	The worst-case execution time tool challenge 2006.	Int. J. Softw. Tools Technol. Transf.	2009	DBLP DOI BibTeX RDF	Embedded systems, Timing analysis, Worst-case execution time, WCET, Hard real time
11	Dariusz Barbucha, Ireneusz Czarnowski, Piotr Jedrzejowicz, Ewa Ratajczak-Ropel, Izabela Wierzbowska	e-JABAT - An Implementation of the Web-Based A-Team.	Intelligent Agents in the Evolution of Web and Applications	2009	DBLP DOI BibTeX RDF	JABAT, A-Team, computionally hard problems, optimization, multi-agents systems
11	Byron J. Gao, Mingji Xia, Walter Cai, David C. Anastasiu	The gardener's problem for web information monitoring.	CIKM	2009	DBLP DOI BibTeX RDF	gardener's problem, multicriteria maintenance scheduling, web information monitoring, np-hard, olap
11	Lasse Kliemann, Anand Srivastav	Experimental Study of Non-oblivious Greedy and Randomized Rounding Algorithms for Hypergraph b-Matching.	SEA	2009	DBLP DOI BibTeX RDF	hypergraph matching, approximation algorithms, greedy algorithms, hybrid algorithms, NP-hard problems, randomized rounding
11	Maik Hadorn, Peter Eggenberger Hotz	Multivesicular Assemblies as Real-World Testbeds for Embryogenic Evolutionary Systems.	ACAL	2009	DBLP DOI BibTeX RDF	Embryogenic evolution, real-world testbed, vesicles, hard sphere colloids, DNA, programmability, self-assembly
11	Kai Lampka, Simon Perathoner, Lothar Thiele	Analytic real-time analysis and timed automata: a hybrid method for analyzing embedded real-time systems.	EMSOFT	2009	DBLP DOI BibTeX RDF	performance analysis, timed automata, hard real-time systems, real-time calculus
11	Stephan Wilhelm, Björn Wachter	Symbolic state traversal for WCET analysis.	EMSOFT	2009	DBLP DOI BibTeX RDF	abstract interpretation, binary decision diagram, worst-case execution time, hard real time, processor models
11	Ireneusz Czarnowski, Piotr Jedrzejowicz, Izabela Wierzbowska	A-Team Middleware on a Cluster.	KES-AMSTA	2009	DBLP DOI BibTeX RDF	JABAT, A-Team, computionally hard problems, cluster, optimization, multi-agents systems
11	Sarvesh Kumar Varatharajan, Gunes Ercal-Ozkaya	On a Local Heuristic for a Reverse Multicast Forwarding Game.	NetCoM	2009	DBLP DOI BibTeX RDF	incentive compatible topology control, heuristics for NP-Hard problems, random Euclidean power graphs, sensor networks, game theory, local algorithm, location based routing
11	Johan Håstad, Mats Näslund	Practical Construction and Analysis of Pseudo-Randomness Primitives.	J. Cryptol.	2008	DBLP DOI BibTeX RDF	Hard core function, One-way function, Pseudo random generator, Exact security
11	Fedor V. Fomin, Fabrizio Grandoni 0001, Dieter Kratsch	Solving Connected Dominating Set Faster than 2 n .	Algorithmica	2008	DBLP DOI BibTeX RDF	Exponential-time exact algorithm, Maximum leaf spanning tree, Connected dominating set, NP-hard problem
11	Jun Yan 0008, Wei Zhang 0002	Analyzing the worst-case execution time for instruction caches with prefetching.	ACM Trans. Embed. Comput. Syst.	2008	DBLP DOI BibTeX RDF	instruction caches, hard real-time, Worst-case execution time analysis, instruction prefetching
11	Davood Shamsi, Farinaz Koushanfar, Miodrag Potkonjak	Challenging benchmark for location discovery in ad hoc networks: foundations and applications.	MobiHoc	2008	DBLP DOI BibTeX RDF	add hoc networks, hard instances, localization, benchmarks, NP-complete problem
11	Ke Zeng, Jianzhong Zhang, Hang Qiu 0002	Real-Time Shadow Research in Virtual Environment with Higher Complexity and Larger Shadow Regions.	PACIIA (1)	2008	DBLP DOI BibTeX RDF	hard shadow, higher complexity and larger shadow regions, real-time shadow, virtual environment, soft shadow
11	Valentin E. Brimkov	Scaling of Plane Figures That Assures Faithful Digitization.	IWCIA	2008	DBLP DOI BibTeX RDF	lattice polygon, polyhedral reconstruction, NP-hard problem, digital geometry, scaling factor
11	Joaquín Izquierdo 0001, Idel Montalvo, Rafael Pérez-García, Mario Tavera	Optimization in water systems: a PSO approach.	SpringSim	2008	DBLP DOI BibTeX RDF	water industry, particle swarm optimization, NP-hard problem, evolutionary optimization
11	Rushil Raghavjee, Nelishia Pillay	An application of genetic algorithms to the school timetabling problem.	SAICSIT	2008	DBLP DOI BibTeX RDF	hard constraints, school timetabling problem, timetabling problems, genetic algorithms
11	Dariusz Barbucha, Ireneusz Czarnowski, Piotr Jedrzejowicz, Ewa Ratajczak-Ropel, Izabela Wierzbowska	Web Accessible A-Team Middleware.	ICCS (3)	2008	DBLP DOI BibTeX RDF	JABAT, A-Team, computionally hard problems, optimization, multi-agents systems
11	László Szilágyi, David Iclanzan, Sándor M. Szilágyi, Dan Dumitrescu	GeCiM: A Novel Generalized Approach to C-Means Clustering.	CIARP	2008	DBLP DOI BibTeX RDF	possibilistic c-means clustering, hard c-means clustering, evolutionary computation, fuzzy c-means clustering
11	Takaaki Okura, Yoko Hirose	Development of a Web Type DVD Viewer Synchronized with Multilingual Captions for Existing DVDs.	ICCHP	2008	DBLP DOI BibTeX RDF	Deaf and Hard of Hearing, e-Learning, Web, Caption, DVD
11	Jittat Fakcharoenphol, Bundit Laekhanukit	An o(log2 k)-approximation algorithm for the k-vertex connected spanning subgraph problem.	STOC	2008	DBLP DOI BibTeX RDF	approximation algorithms for NP-hard problems, k-connected spanning subgraphs, network design
11	Santiago Urueña, José Antonio Pulido, Jorge López, Juan Zamorano, Juan Antonio de la Puente	A New Approach to Memory Partitioning in On-Board Spacecraft Software.	Ada-Europe	2008	DBLP DOI BibTeX RDF	Ravenscar Ada, integrated modular avionics, embedded systems, hard real-time, high-integrity
11	Jing-Fa Liu, Wen-Qi Huang	Quasi-Physical Algorithm of an Off-Lattice Model for Protein Folding Problem.	J. Comput. Sci. Technol.	2007	DBLP DOI BibTeX RDF	off-lattice model, quasi-physical algorithm, off-trap strategy, protein folding, NP-hard problem
11	Randeep Bhatia, Julia Chuzhoy, Ari Freund 0001, Joseph Naor	Algorithmic aspects of bandwidth trading.	ACM Trans. Algorithms	2007	DBLP DOI BibTeX RDF	Approximation algorithms for NP-hard problems, scheduling, resource allocation, dynamic storage allocation, general caching
11	Aggelos Ioannou, Manolis Katevenis	Pipelined heap (priority queue) management for advanced scheduling in high-speed networks.	IEEE/ACM Trans. Netw.	2007	DBLP DOI BibTeX RDF	high-speed network scheduling, pipelined hard-ware heap, synthesizable core, weighted fair queueing, priority queue, weighted round robin
11	Xiaoning Ding, Song Jiang 0001, Feng Chen 0005	A buffer cache management scheme exploiting both temporal and spatial localities.	ACM Trans. Storage	2007	DBLP DOI BibTeX RDF	Caching, file systems, temporal locality, spatial locality, hard disk
11	Jingui Huang, Jianer Chen, Songqiao Chen, Jianxin Wang 0001	A simple linear time approximation algorithm for multi-processor job scheduling on four processors.	J. Comb. Optim.	2007	DBLP DOI BibTeX RDF	Multi-processor job scheduling, Approximation algorithm, NP-hard problem
11	Clayton W. Commander, Panos M. Pardalos, Valeriy Ryabchenko, Stan Uryasev, Grigoriy Zrazhevsky	The wireless network jamming problem.	J. Comb. Optim.	2007	DBLP DOI BibTeX RDF	Network interdiction, Percentile constraints, Integer programming, NP-hard, Jamming
11	Shuqiang Chen, Qizhi Fang	Call Control and Routing in SONET Rings.	ESCAPE	2007	DBLP DOI BibTeX RDF	SONET ring, routing, approximation algorithm, hard, call
11	Jun Yan 0008, Wei Zhang 0002	WCET analysis of instruction caches with prefetching.	LCTES	2007	DBLP DOI BibTeX RDF	instruction cache, hard real-time, worst-case execution time analysis, instruction prefetching
11	Jouko Kokko, Erkki Kemppainen, Aulikki Rautavaara	Technology and Regional Social Structures: Evaluation of Remote Sign Language Interpretation in Finland.	HCI (5)	2007	DBLP DOI BibTeX RDF	Interpretation service, hard of hearing people, Disability, ICT
11	Yu-Hang Tsai, Kuochen Wang, Jheng-Ming Chen	A deferred-workload-based inter-task dynamic voltage scaling algorithm for portable multimedia devices.	IWCMC	2007	DBLP DOI BibTeX RDF	actual workload, deferred-workload-based, inter-task dynamic voltage scaling, worst-case execution time, hard real-time system, slack time
11	Qunwei Zheng, Sibabrata Ray, Xiaoyan Hong, Lei Tang, Li Gao	Integrity and its applications.	ACM Southeast Regional Conference	2007	DBLP DOI BibTeX RDF	integrity, NP-hard
11	Jürg Wullschleger	Oblivious-Transfer Amplification.	EUROCRYPT	2007	DBLP DOI BibTeX RDF	oblivious-transfer amplification, universal oblivious transfer, weak oblivious transfer, computational weak oblivious transfer, distributed leftover hash lemma, hard-core lemma
11	Florian Eibensteiner, Rainer Findenig, Jürgen Tossold, Wilfried Kubinger, Josef Langer, Markus Pfaff	Embedded Robotic Solution: Integrating Robotics Interfaces with a High-Level CPU in a System-on-a-Chip.	EUROCAST	2007	DBLP DOI BibTeX RDF	Robotics, System-on-a-Chip, hard real-time, RTOS
11	Lap Chi Lau, Joseph Naor, Mohammad R. Salavatipour, Mohit Singh	Survivable network design with degree or order constraints.	STOC	2007	DBLP DOI BibTeX RDF	approximation algorithms, network design, NP-hard problems, bounded degree, iterative rounding
11	Ratnabali Biswas, Kaushik R. Chowdhury, Dharma P. Agrawal	Attribute Allocation and Retrieval Scheme for Large-Scale Sensor Networks.	Int. J. Wirel. Inf. Networks	2006	DBLP DOI BibTeX RDF	storage node, control node, correlation tree, aggregation tree, hard threshold, update epoch, Data-centric storage, soft threshold, allocation problem
11	Kun-Feng Lin, Chuan-Ming Liu	Broadcasting dependent data with minimized access latency in a multi-channel environment.	IWCMC	2006	DBLP DOI BibTeX RDF	broadcasting, latency, NP-hard, DAG, multiple channels
11	Guodong Rong, Tiow Seng Tan	Utilizing jump flooding in image-based soft shadows.	VRST	2006	DBLP DOI BibTeX RDF	hard shadow, penumbra map, interactive application, programmable graphics hardware, game programming, parallel prefix
11	D. Kebbal	Automatic Flow Analysis Using Symbolic Execution and Path Enumeration.	ICPP Workshops	2006	DBLP DOI BibTeX RDF	static WCET analysis, automatic parametric flow analysis, block-based symbolic execution, path enumeration, hard real-time systems
11	Andreas Ermedahl, Friedhelm Stappert, Jakob Engblom	Clustered Worst-Case Execution-Time Calculation.	IEEE Trans. Computers	2005	DBLP DOI BibTeX RDF	WCET calculation, embedded systems, hard real-time, WCET analysis
11	Wieslaw Kubiak	Solution of The Liu-Layland Problem Via Bottleneck Just-In-Time Sequencing.	J. Sched.	2005	DBLP DOI BibTeX RDF	just-in-time sequencing, the Liu-Layland problem, apportionment problem, hard real-time systems, periodic scheduling
11	Xiaodong Gu, Guoliang Chen 0001, Yinlong Xu	Average-Case Performance Analysis of a 2D Strip Packing Algorithm-NFDH.	J. Comb. Optim.	2005	DBLP DOI BibTeX RDF	average-case performance ratio, worst-case performance ratio, approximation algorithm, NP-hard, bin packing
11	Ratnabali Biswas, Kaushik R. Chowdhury, Dharma P. Agrawal	Attribute allocation in large scale sensor networks.	DMSN	2005	DBLP DOI BibTeX RDF	correlation tree, hard threshold, query dissemination, aggregation, minimum spanning tree, in-network processing, data retrieval, data-centric storage, soft threshold, allocation problem
11	David M. Cherba, William F. Punch, Phillip M. Duxbury, Simon J. L. Billinge, Pavol Juhas	Conformation of an ideal bucky ball molecule by genetic algorithm and geometric constraint from pair distance data: genetic algorithm.	GECCO	2005	DBLP DOI BibTeX RDF	NP-hard search, bucky ball, spatial crossover, genetic algorithm, molecular conformation
11	Alexandr Andoni, Jessica Staddon	Graceful service degradation (or, how to know your payment is late).	EC	2005	DBLP DOI BibTeX RDF	degradation scheme, moderately-hard functions, revocation scheme, copyright protection, broadcast encryption
11	Ali El-Haj-Mahmoud, Ahmed S. Al-Zawawi, Aravindh Anantaraman, Eric Rotenberg	Virtual multiprocessor: an analyzable, high-performance architecture for real-time computing.	CASES	2005	DBLP DOI BibTeX RDF	worst-case execution time, schedulability analysis, superscalar processor, simultaneous multithreading, hard real-time, resource partitioning
11	Paolo Donzelli	A goal-driven and agent-based requirements engineering framework.	Requir. Eng.	2004	DBLP DOI BibTeX RDF	Soft and hard goals, UML, Agents, Requirements engineering, Non-functional requirements, Quality models
11	Lui Sha, Tarek F. Abdelzaher, Karl-Erik Årzén, Anton Cervin, Theodore P. Baker, Alan Burns 0001, Giorgio C. Buttazzo, Marco Caccamo, John P. Lehoczky, Aloysius K. Mok	Real Time Scheduling Theory: A Historical Perspective.	Real Time Syst.	2004	DBLP DOI BibTeX RDF	dynamic-priority scheduling, new challenges, feedback, earliest deadline first, fixed-priority scheduling, hard real-time, soft real-time, rate-monotonic scheduling, scheduling models
11	Giacomo Bucci, Andrea Fedeli, Luigi Sassoli, Enrico Vicario	Timed State Space Analysis of Real-Time Preemptive Systems.	IEEE Trans. Software Eng.	2004	DBLP DOI BibTeX RDF	nondeterministic time parameters, timeliness predictability, Preemptive Time Petri Nets, reactive systems, multiprocessor schedulability, Hard real-time systems, interprocess communication, preemptive scheduling, state space analysis
11	Rodney Turner, Glenn Lowry, Julie Fisher	A Structural Model of the Information Systems Professional.	Information and Communication Technologies and Real-Life Learning	2004	DBLP DOI BibTeX RDF	IS graduates, technical skills, hard skills, Information Systems, structural model, soft skills, IS professional
11	Salvatore Cavalieri, Salvatore Monforte, Angelo Corsaro, Giovanni Scapellato	Multicycle Polling Scheduling Algorithms for FieldBus Networks.	Real Time Syst.	2003	DBLP DOI BibTeX RDF	FieldBus communication networks, hard real-time scheduling, priority scheduling algorithm, earliest deadline first algorithm, rate monotonic algorithm
11	Oded Goldreich 0001, Vered Rosen	On the Security of Modular Exponentiation with Application to the Construction of Pseudorandom Generators.	J. Cryptol.	2003	DBLP DOI BibTeX RDF	Hard-core predicates, Simultaneous security, Factoring assumption, Discrete logarithm, Pseudorandom generator, Modular exponentiation
11	Jakob Engblom, Andreas Ermedahl, Mikael Sjödin, Jan Gustafsson, Hans Hansson	Worst-case execution-time analysis for embedded real-time systems.	Int. J. Softw. Tools Technol. Transf.	2003	DBLP DOI BibTeX RDF	Embedded systems, Software architecture, Hard real-time, WCET analysis, Programming tools
11	Giacomo Bucci, Andrea Fedeli, Enrico Vicario	Predicting Timeliness of Reactive Systems under Flexible Scheduling.	ISADS	2003	DBLP DOI BibTeX RDF	flexible computation, enumerative analysis, Petri nets, validation, hard real time systems, process scheduling, timed behavior
11	Vittoria Bruni, Domenico Vitulano	A Wiener filter improvement combining wavelet domains.	ICIAP	2003	DBLP DOI BibTeX RDF	Signal and Image Denoising, Hard-Thresholding, Wavelet Transform, Wiener Filter
11	Andreas Ermedahl, Friedhelm Stappert, Jakob Engblom	Clustered calculation of worst-case execution times.	CASES	2003	DBLP DOI BibTeX RDF	WCET calculation, embedded systems, hard real-time, WCET analysis
11	Ioannis C. Avramopoulos, Miltiades E. Anagnostou	Optimal Component Configuration and Component Routing.	IEEE Trans. Mob. Comput.	2002	DBLP DOI BibTeX RDF	component allocation, component mobility, multiterminal cuts, max flow—min cut, mixed binary integer programming, Mobile agents, reconfiguration, NP-hard problems
11	Paolo Donzelli, Roberto Setola	Handling the knowledge acquired during the requirements engineering process: a case study.	SEKE	2002	DBLP DOI BibTeX RDF	soft and hard goals, agents, requirements engineering, process modeling, quality modeling
11	Johan Håstad	Some optimal inapproximability results.	J. ACM	2001	DBLP DOI BibTeX RDF	NP-hard optimization problems, max-sat, linear equations, Inapproximability, probabilistically checkable proofs
11	Amotz Bar-Noy, Reuven Bar-Yehuda, Ari Freund 0001, Joseph Naor, Baruch Schieber	A unified approach to approximating resource allocation and scheduling.	J. ACM	2001	DBLP DOI BibTeX RDF	Approximation algorithms for NP-hard problems, scheduling, resource allocation, dynamic storage allocation, general caching
11	Carsten Wegener, Michael Peter Kennedy, Bernd Straube	Process Deviations and Spot Defects: Two Aspects of Test and Test Development for Mixed-Signal Circuits.	J. Electron. Test.	2001	DBLP DOI BibTeX RDF	hard-fault, test pattern selection, soft-fault
11	Friedhelm Stappert, Andreas Ermedahl, Jakob Engblom	Efficient longest executable path search for programs with complex flows and pipeline effects.	CASES	2001	DBLP DOI BibTeX RDF	pipeline timing, program flow, embedded systems, WCET, hard real-time, path search
11	Kang G. Shin, Chih-Che Chou, Seok-Kyu Kweon	Distributed Route Selection for Establishing Real-Time Channels.	IEEE Trans. Parallel Distributed Syst.	2000	DBLP DOI BibTeX RDF	Hard real-time communication systems, real-time channel/connection, deadline guarantees, distributed route selection, message scheduling
11	Martin Skutella	Approximating the single source unsplittable min-cost flow problem.	FOCS	2000	DBLP DOI BibTeX RDF	single source unsplittable min-cost flow problem, common source vertex, destination vertices, edge capacities, virtual-circuit routing, hard cost constraints, computational complexity, load balancing, resource allocation, combinatorial optimization, partitioning, optimisation, processor scheduling, NP-complete problems, packing, hardness, bicriteria approximations
11	Maxim Sviridenko, Gerhard J. Woeginger	Approximability and in-approximability results for no-wait shop scheduling.	FOCS	2000	DBLP DOI BibTeX RDF	in-approximability results, no-wait shop scheduling, makespan criterion, computational complexity, approximability, processor scheduling, polynomial time approximation scheme, polynomial approximation, APX-hard
11	Rafail Ostrovsky, Yuval Rabani	Polynomial Time Approximation Schemes for Geometric k-Clustering.	FOCS	2000	DBLP DOI BibTeX RDF	geometric k-clustering, data point clustering, data set partitioning, high dimensional geometry, binary cube, computational complexity, computational geometry, Hamming distance, NP-hard problem, distance function, polynomial time approximation schemes, pattern clustering, k-median problem
11	Jan Lindström, Kimmo E. E. Raatikainen	Using importance of transactions and optimistic concurrency control in firm real-time databases.	RTCSA	2000	DBLP DOI BibTeX RDF	optimistic concurrency control protocol, transaction importance, hard real-time databases, database consistency requirements, heterogeneous transactions, OCC-PDATI, serialization order dynamic adjustment, prototype database system, performance, real-time systems, concurrency control, timing, database management systems, transaction processing, timing constraints, conflict resolution, access protocols
11	Enzo Mumolo	Prediction of Disk Arm Movements in Anticipation of Future Requests.	MASCOTS	1999	DBLP DOI BibTeX RDF	disk arm, seek time, prediction, hard disk
11	Jakob Engblom, Andreas Ermedahl	Pipeline Timing Analysis Using a Trace-Driven Simulator.	RTCSA	1999	DBLP DOI BibTeX RDF	pipeline analysis, embedded systems, WCET, hard real-time
11	Joël Goossens, Raymond R. Devillers	Feasibility Intervals for the Deadline Driven Scheduler with Arbitrary Deadlines.	RTCSA	1999	DBLP DOI BibTeX RDF	hard real-time scheduling, periodic task set, feasibility interval, Deadline driven scheduler, arbitrary deadline
11	Franz Fischer, Annette Muth, Georg Färber	Towards interprocess communication and interface synthesis for a heterogeneous real-time rapid prototyping environment.	CODES	1998	DBLP DOI BibTeX RDF	task classification model, rapid prototyping, SDL, hard real-time, communication synthesis
11	Jan Jonsson, Kang G. Shin	A Parametrized Branch-and-Bound Strategy for Scheduling Precedence-Constrained Tasks on a Multiprocessor System.	ICPP	1997	DBLP DOI BibTeX RDF	real-time scheduling precedence-constrained tasks, branch-and-bound strategy, multiprocessor systems, hard real-time systems
11	Spyros Tragoudas	Min-Cut Partitioning on Underlying Tree and Graph Structures.	IEEE Trans. Computers	1996	DBLP DOI BibTeX RDF	Circuit and network partitioning, NP-hard, iterative improvement
11	Chihping Wang, Ming-Syan Chen	On the Complexity of Distributed Query Optimization.	IEEE Trans. Knowl. Data Eng.	1996	DBLP DOI BibTeX RDF	semijoin processing, complexity, distributed databases, NP-hard problems, Distributed query optimization
11	Sha Guo, Wei Sun 0002, Mark Allen Weiss	On Satisfiability, Equivalence, and Impication Problems Involving Conjunctive Queries in Database Systems.	IEEE Trans. Knowl. Data Eng.	1996	DBLP DOI BibTeX RDF	derivability problem, Database, NP-hard, satisfiability, conjunctive queries, implication problem
11	Prasad Chalasani, Somesh Jha, Isaac Saias	Approximate Option Pricing.	FOCS	1996	DBLP DOI BibTeX RDF	approximate option pricing, world financial markets, binomial pricing model, stock price, path-dependent options, #-P hard, deterministic polynomial-time approximate algorithms, perpetual American put option, random walk, random walks, error analysis, Monte Carlo methods, Monte Carlo methods, polynomial time, error bounds, computational problem
11	Claire Kenyon, Eric Rémila	Approximate Strip Packing.	FOCS	1996	DBLP DOI BibTeX RDF	packing rectangles, NP-hard cutting-stock problem, fractional bin-packing, guillotine cuts, computational complexity, strip-packing
11	Alan M. Frieze, Ravi Kannan	The Regularity Lemma and Approximation Schemes for Dense Problems.	FOCS	1996	DBLP DOI BibTeX RDF	dense problems, polynomial time approximation, dense graphs, Graph Bisection problem, Min l-way cut problem, Graph Separator problem, Max-SNP hard problems, graph theory, approximation schemes, Quadratic Assignment Problem, regularity lemma, Max Cut problem
11	Jon M. Kleinberg	Single-Source Unsplittable Flow.	FOCS	1996	DBLP DOI BibTeX RDF	max-flow min-cut, scheduling, load balancing, generalization, NP-hard, unsplittable flow, machine scheduling, capacity constraints
11	Stephen Docy, Inki Hong, Miodrag Potkonjak	Throughput Optimization in Disk-Based Real-Time Application Specific Systems.	ISSS	1996	DBLP DOI BibTeX RDF	Massive Storage, Hard Real-Time, System-Level Synthesis
11	Almut Burchard, Jörg Liebeherr, Yingfeng Oh, Sang Hyuk Son	New Strategies for Assigning Real-Time Tasks to Multiprocessor Systems.	IEEE Trans. Computers	1995	DBLP DOI BibTeX RDF	task assignment scheme, multiprocessor systems, Hard real-time systems, periodic tasks, rate-monotonic scheduling
11	Jin-yi Cai, D. Sivakumar	The Resolution of a Hartmanis Conjecture.	FOCS	1995	DBLP DOI BibTeX RDF	Hartmanis conjecture, sparse sets, logspace many-one reductions, sparse hard set, computational complexity
11	Sanjeev Arora	Reductions, Codes, PCPs, and Inapproximability.	FOCS	1995	DBLP DOI BibTeX RDF	NP-hard functions, code-like Levin reduction, complexity assumption, positive fraction, 3-colorable graph, code-like reduction, computational complexity, graph theory, error correction codes, error-correcting codes, NP-hardness, codes, inapproximability, PCPs, hardness, approximation ratio
11	Guy Even, Joseph Naor, Satish Rao, Baruch Schieber	Divide-and-Conquer Approximation Algorithms via Spreading Metrics (Extended Abstract).	FOCS	1995	DBLP DOI BibTeX RDF	divide-and-conquer approximation algorithms, spreading metrics, NP-hard graph optimization problems, graph optimization problems, fractional spreading metric, fractional lengths, optimisation problem, spreading metric, interval graph completion, storage-time product, computational complexity, optimisation, directed graphs, directed graphs, polynomial time, vertices, divide and conquer methods, multicuts, polynomial time approximation algorithm
11	Martin Fürer	Improved Hardness Results for Approximating the Chromatic Number.	FOCS	1995	DBLP DOI BibTeX RDF	hardness results, chromatic number approximation, geometric proof, randomized twisting method, amortized free bits, polynomial lower bounds, computational complexity, graph theory, NP-hard, polynomial time algorithm, chromatic number
11	Mark G. Karpovsky, Lev B. Levitin, Feodor S. Vainstein	Diagnosis by Signature Analysis of Test Responses.	IEEE Trans. Computers	1994	DBLP DOI BibTeX RDF	faulty processing elements, compressed test response, space-time signature, hard decision decoding, space-time compression, parallel processing, fault tolerant computing, logic testing, fault location, array processors, signature analysis, test responses
11	Doowon Paik, Sudhakar M. Reddy, Sartaj Sahni	Deleting Vertices to Bound Path Length.	IEEE Trans. Computers	1994	DBLP DOI BibTeX RDF	vertex deletion problem, path length bound, weighted directed acyclic graphs, quadratic time, computational complexity, directed graphs, NP-hard problems, linear time, series-parallel graph, rooted tree
11	Bing-rung Tsai, Kang G. Shin	Assignment of Task Modules in Hypercube Multicomputers with Component Failures for Communication Efficiency.	IEEE Trans. Computers	1994	DBLP DOI BibTeX RDF	task modules, indirect optimization, communication turnaround time, optimization, performance measure, hypercube networks, telecommunication traffic, communication cost, fault-tolerant routing, task assignment, NP hard problem, link failures, hypercube multicomputers, communication efficiency, component failures, communication traffic
11	Carsten Lund, Mihalis Yannakakis	On the Hardness of Approximating Minimization Problems.	J. ACM	1994	DBLP DOI BibTeX RDF	clique cover, approximation algorithms, NP-hard, graph coloring, dominating set, set cover, independent set, chromatic number, probabilistically checkable proofs, hitting set
11	Eileen Tien Lin, Edward Omiecinski, Sudhakar Yalamanchili	Large Join Optimization on a Hypercube Multiprocessor.	IEEE Trans. Knowl. Data Eng.	1994	DBLP DOI BibTeX RDF	large join optimization, parallel large join plan, initial solution, iterative local-improvement method, Intel iPSC/2 hypercube machine, performance, computational complexity, parallel programming, query processing, relational database, heuristics, simulated annealing, optimisation, iterative methods, hypercube networks, relational algebra, heuristic programming, NP-hard problem, hypercube multiprocessor, problem complexity, inherent parallelism, large join queries
11	R. Ravi 0001	Rapid Rumor Ramification: Approximating the minimum broadcast time (Extended Abstract)	FOCS	1994	DBLP DOI BibTeX RDF	minimum gossip time problem, rapid rumor ramification, minimum broadcast time approximation, minimum broadcast time problem, telephone model, multicast problem, NP-complete, NP-hard, undirected graph, conference calls
11	Haim Kaplan, Ron Shamir, Robert Endre Tarjan	Tractability of parameterized completion problems on chordal and interval graphs: Minimum Fill-in and Physical Mapping	FOCS	1994	DBLP DOI BibTeX RDF	added edges, parameterized completion problems, minimum fill-in, NP-Hard graph completion problem, interval graphs, parameterized complexity, tractability, vertex coloring, physical mapping
11	S. Rao Kosaraju, James K. Park, Clifford Stein 0001	Long Tours and Short Superstrings (Preliminary Version)	FOCS	1994	DBLP DOI BibTeX RDF	shortest-superstring problem, short superstrings, long tours, weight-maximizing variants, weight-minimizing counterparts, nontrivial approximation algorithms, directed graphs, traveling-salesman problems, undirected graphs, MAX SNP-hard
11	Noga Alon, Alan M. Frieze, Dominic Welsh	Polynomial time randomised approxmiation schemes for the Tutte polynomial of dense graphs	FOCS	1994	DBLP DOI BibTeX RDF	polynomial time randomised approximation schemes, dense graphs, Tutte-Grothendieck polynomial, combinatorial quantities, spanning forests, strongly connected orientations, k-colorings, reliability probability, P-hard, ferromagnetic Q-state Potts model, linear matroids, weight enumerator, linear codes, partition functions, Tutte polynomial
11	David Hung-Chang Du, Ichiang Lin, K. C. Chang 0001	On Wafer-Packing Problems.	IEEE Trans. Computers	1993	DBLP DOI BibTeX RDF	wafer-packing problems, multiple chip designs, fabrication cost, VLSI, NP-hard, heuristic algorithms, VLSI design, multichip modules, polynomial-time solvable
11	Anindo Bagchi, S. Louis Hakimi, Edward F. Schmeichel	Gossigping in a Distributed Network.	IEEE Trans. Computers	1993	DBLP DOI BibTeX RDF	radio links, computational complexity, distributed algorithm, distributed algorithms, NP-hard, gossiping, distributed network, broadcast networks, point-to-point networks
11	Edward P. F. Chan	A Possible World Semantics for Disjunctive Databases.	IEEE Trans. Knowl. Data Eng.	1993	DBLP DOI BibTeX RDF	ground atom, disjunctive database, generalized closed world assumption, GCWA, disjunctive database rule, DDR, PWS, propositional databases, negative ground literal, co-NP-hard, knowledge based systems, database theory, deductive databases, database semantics, possible world semantics, negative information
11	Sanjeev Arora, László Babai, Jacques Stern, Z. Sweedyk	The Hardness of Approximate Optimia in Lattices, Codes, and Systems of Linear Equations	FOCS	1993	DBLP DOI BibTeX RDF	approximate optima, NP-hard, lattices, codes, polynomial time algorithm, linear equations, interactive proof systems, hardness, set-cover problem, binary codes
11	Douglas M. Blough, Andrzej Pelc	Complexity of Fault Diagnosis in Comparison Models.	IEEE Trans. Computers	1992	DBLP DOI BibTeX RDF	ault diagnosis, comparison models, comparison-based probabilistic model, optimal diagnosis, asymmetric comparison model, ring systems, computational complexity, grids, fault tolerant computing, multiprocessor, hypercubes, multiprocessing systems, NP-hard, fault location, bipartite graphs, linear-time algorithm, forests